Before you format try using Ad-aware and Spybot.

In addition, clean out your "Temp" and "Temp Internet Files" folders completely.

I'll bet that should free up a bit of space :)