These sorts of things can happen regardless of ISP, so it's important to find the root cause of the problem. While dumping AOL is a good idea for many reasons, none of them involve the avoiding of a repeat performance of this incident.
The first major red flag that goes up for me, is when you say you "removed loads of programs" after running virus and spyware scans. This means that you need to alter some of your computing habits. No virus scanner is 100%, nor is any spyware scanner. To make matters even more fun, there's a special type of program that can mask itself from a virus scanner called a rootkit.
Sounds to me like you were infested with, and still are, some password sniffing program. At this point, I would be checking all my credit cards for any activity that isn't yours, and consider altering the credit card companies to flag your accounts for extra fraud vigil. I would then immediately format my system to be sure I cleaned up everything. I would make sure I've got all the latest updates for my operating system, and I would proceed to avoid Internet Explorer like it were a leper. Opting for something like Mozilla Firefox. This is on top of making sure I've got a virus scanner running and continually updated and the other usual stuff. Make sure the user account you create on Windows has a password on it, and it's one you've never used before. Be sure to put a password on the Administrator account. (if you're using XP, since XP neglects to ever inform you that the account even exists)
If you want to take things a step further, you could load on some Linux distribution or buy yourself a Mac. I'm sure some day someone will make it easy to write cross platform attacks, and then Linux and the Mac will be targeted, but until that day arrives you could rest quite a bit easier in terms of security.