sponsored links

Hi, have recently started getting “sponsored links” appearing on websites that didn’t used to be there. They are not the proper sponsored links with double underlining taking you to an actual site sponsor website, but ones where the writing is green and has a single underline, and can be part of a word rather than the full word, e.g. notifiCATion comes up with sponsored link and the little yellow description box saying "best cat". They all take you to various gambling, porn etc. websites, so I am suspecting spyware. I’ve run Norton, ad-aware se, and spybot S&D, and none of them seem to remove it. I’m also suspecting a hijacking as my pc has slowed down a bit of late as well.
I think it has something to do with begin2search.com? but have no idea where it came from. I have un-installed some programs that I had installed around the time the prob started, but it doesn’t seem to be related in anyway.

Any ideas would be greatly appreciated. Thankski