If evil is right, then I have to repeat reinstalling IE would be pointless, it'd be like having a bad engine on a car and replacing the exhaust system, it's not going to do anything.

Even if it isn't malware related, it's still a good idea to have a copy of malwarebytes on your system. Download the free version and run a scan. If you can't do it on the affected computer, download it on another, put it on a flash drive or burn it on a dvd and put it on your system that way.

http://www.malwarebytes.org/