Okay, here's what I got....
It's good that you got rid of Ad-free. Chances are if a program wigs out and things start getting funky said program is responsible for funkiness. (I hope that made sense...
)
I would say that it is important to get rid of the whole enchilada and am going to assume that you followed its uninstall program to get rid of it. I know sometimes they're tricky to get rid of and sometimes stuff hangs around. I ran a couple of searches through Google and didn't find anybody with any uninstall problems with Ad-free so take that for what it's worth.
If you want to mess with it. Your HOSTS file is located at C:\windows and might be hidden. It seems that Ad-Free uses a HOSTS file to block unsavory pop ups, banner ads, and unwanted pop-unders, so you'll probably see some strange stuff in there when you find it. I would probably just rename it something generic and then see if that fixes the problem.
I also ran across a couple of mentions about firewalls and anti-virus stuff. Seems that some firewalls and anti-virus software (if it's loading from startup, which AVG has the option to do...) have a problem with not letting images load until you right-click them. Maybe your version was corrupted in the ad-blitz or during a routing upgrade. Although most of the popular firewalls and anti-virus software was mentioned, Norton seems to be the biggest offender. You didn't mention running a firewall, but I figured I'd throw that in.
So, you might turn all that junk off and see if that fixes it.
If none of that works here's a link to the Microsoft Knowledge Base.
http://support.microsoft.com/?kbid=283807
It mentions an encoding problem and a registry edit, so buyer beware
If all else fails...I would just upgrade IE. MyIE is a great program, I've been running it for months and can't remember the last pop-up I had.
I know that was long winded, but I hope
something there helps to fix the problem or, at the very least, leads you to the right solution.
good luck and let us know how it turns out