IE has always had problems retrieving and caching favicons. Microsoft has never put much (any?) effort into correcting the problem, either. It's been there for as long as I can remember, but at least since IE 6. A quick Internet search shows many similar complaints and no solutions. You can search for "IE X favicons" (with 6, 7, 8, and 9 for X) and you'll get the same reports.
I don't believe Moab's assertion that history expiration is to blame, nor that history is a bad place to store favicons. Chrome and Firefox use History and Cache to store favicons.... although more recent versions of Firefox use Places, and it's is extremely difficult to remove favicons in Firefox now.