I found a stupid solution on the internet today:
<link rel="shortcut icon" href="/favicon.ico?">
The ? is the key - just the link didn't do it.
IE8 Team - are you listening? How about fixing some nagging little issues like this, and the insane caching that breaks all the rules, and the spidered history files all over the hard drive?