Hmm... definitely a strange one. I think what I might do if it was my machine is make a restore point, or better yet, a system image. Then check to see if IE9 can be uninstalled from View Installed Updates > Uninstall An Update. (This may not be possible if IE9 was pre-installed. The OEM manufacturer may have removed IE8 completely. Uninstalling IE9 under those circumstances could leave the computer without a browser to revert back to.)
But if you can completely uninstall IE9 and go back to IE8, I'd use the registry cleaner in CCleaner if you haven't already done that. Then run a System File Checker scan from an elevated command prompt (option two) just to make sure there's no damaged or corrupt system files (which could have damaged or corrupted the IE9 files.) If the scan finds any problems, run it 3 times, rebooting in between each scan. Then I'd try reinstalling IE9 on a (hopefully) clean Windows 7 platform. SFC /SCANNOW Command - System File Checker
It doesn't sound like a malware issue to me, especially since Malwarebytes and MSE didn't show anything. Of course, you could always run some additional free on-demand scanners like Hitman Pro, Superantispyware, ESET Online Scanner, etc just to play it safe.