The only other thing I can think of at the moment is a third-party plugin gone awry. To see if this is the case, go to the Addvanced tab again and uncheck “Allow third party browser extensions”. Click OK. You definitely need to restart IE after this change. It might even be a good idea to reboot your computer entirely just to refresh everything. If this fixes the problem, then you know you have an issue with a third-party product. At this point, you’ll need to start uninstalling them one at a time (after re-emnabling third party extensions) until you find the one that makes the problem go away again.
Spy/mal/crap ware is also a possibility, as always. Try the usual Spybot, Adaware and whatever other spyware detection/removal tools others have mentioned here.
Whaty OS and version of IE are you using?