Wow this sure is an odd problem. Many have had similar errors but it seems you tried all their fixes with no luck.

That leaves WAGs for possible suggestions. I might suggest resetting IE. Tools > Internet Options > Advanced. You will have reinstall your add-in but IE will be back at baseline.

I might also run Secunia PSI to make sure all is current.

Jim23 found this, worth a try:

Download details: Windows XP Patch: Directory Corruption Disables XP Search Companion