Gerade festgestellt, dass das Problem auch bei Google Chrome auftritt
Das bestätigt die Vermutung, dass sich da etwas im kompletten System verankert hat.
Es läuft immer noch das von Zacherl genannte Programm SpyBot. Allerdings hat dieses gerade vllt. was Hilfreiches gefunden. Hört sich zumindest vielversprechend an: PBHotbar.SearchAssistant
Klingt sehr nach dieser Art von AdWare, die ich bei dir vermute
Meistens sind die Dinger zum Glück recht einfach zu entfernen.