|As you probably already know, the normal location for IE Favorites is:|
"c:\Documents and Settings\<user>\Favorites".
It might be worth you copying the Favorites folder elsewhere for security while you investigate this issue.
There are quite a few Google hits for changing the location of favorites. I realise you don't want to do this but you might be able to work backwards as it were and fathom something out. There are also registry entries involved.
TweakUI also has a feature for changing favorites location - again this might give some clue as to where IE "thinks" they are.
This link looks particularly useful:
I'm sure there is a way round this but it's not something I know about off the top of my head. Good hunting - glad to have helped on the first bit.
Always pop back and let us know the outcome - thanks