Thanks for the tip Randall.
In fact, I had a 6-months old version of Ad Aware installed and scheduled to run every Friday evening. It even used to come up with one or two spyware components now and then and I felt so confident about my supremacy over these ads.
It was only today I noticed a slight delay in IE start-up and a strange popup add from nowhere. Immediately I installed the latest version of Ad Aware, and oh god, 51 bl**dy spyware entries in my registry, 3 folders and many many more files!!

Yeah Mr. BonzyBuddy was there, hidden this time!
And the fact is I hardly use IE at all. I normally browse with Opera, and thank god, its definitely a lot better. I lately installed and uninstalled Kazaa and iMesh, and they might have been the culprits.