Just seems to happen when using inPrivate browsing yet all other websites I go to show their favicon just fine on all pages using inPrivate browsing.

I did not change the theme, it says in the header element on affected pages

<link href="http://mydomain.com/themes/default/images/favicon.ico" rel="shortcut icon">

Going directly to

http://mydomain.com/themes/default/images/favicon.ico

shows the favicon