Of course you already tried a system restore right?
Is their any chance that IE is corrupt either by spyware like you said our for some other reason? Have you tried reinstalling IE or using the WinXP bootable install disk to check and repair Windows?