Did you ensure that the properly resized window was the last one you closed? The last to close sets the size for the next use.
If that's not it, there are registry hacks that you can copy from various sites to set the size or you can do the following to reset to default:
Close all instances of Internet Explorer. Run regedit. Go to HKEY_CURRENT_USER \ Software \ Microsoft \ Internet Explorer \ Main and delete the value Window_Placement. Close regedit.
If in doubt, save a copy of the value (using File > Export in regedit) before deleting.
I tried all that you suggested, but nothing helped, I'm afraid. Adaware, Spybot and those didn't find anything...
In the end, I was so annoyed, that I deleted all kind of stuff on my computer (movie clips, music, programs, that I didn't use and stuff like that. All that I had downloaded.
Now it works fine again, so I guess one of those files was to blame.