>>> I have full, paid up version AVG Internet Security.
No security suite can block all malware. That's why it's essential to top it up with the free version of Malwarebytes Anti-Malware:
https://www.malwarebytes.org/antimalware/
(NB: If installing it, take care to deselect the option to take a free trial of the Premium version).
However I'm still concerned that it might be a full-blown virus (posing as Internet Explorer) rather than some relatively benign malware. (The Head of Security at Symantec, which makes Norton software, is on record as saying that the very best anti-virus products are only around 60% effective). If you're able to run a full scan with AVG, I'd suggest giving it a go.
Otherwise, if you've got the Windows installation disc, put it in your CD/DVD drive and boot from it. (You might need to go into the BIOS settings to change the boot order if your computer isn't already configured to look for boot files from the CD drive first). Then use the 'Repair' option.