Well, you did not specify what kind of browser you are using, but if it is IE, I would recommend a complete deinstall\reinstall if the problem persists.
But you should still clear cache and history, check for heavy fragmentation, and make sure you are not running multiple instances of IE (task manager, processes, then kill all IE processes and start over). Then I would reinvestigate your malware issues.
Depending on how you found and removed the malware, you may still have issues. I recommend turning off all pop-ups (IE, tools, popup blocker) to stop new malware from being installed. Also, it is very important that you NOT visit sites that are prone to malware (porno being one). If you surf to satisfy your earthly lusts, your system may pay the price.
I recommend two pieces of spyware removal software: Adaware and Spybot:
http://www.lavasoftusa.com/software/adaware/
http://www.safer-networking.org/en/download/
They both work well, but I prefer to run them back-to-back when a machine is heavily "infected" with malware (or suffering from unusual slowness). They compliment each other.
Download and run both of these. You might be surprised as to what you find.