Ich würde mal hingehen und unter %appdata% alle Mozilla Firefox zugehörigen Verzeichnisse löschen.
Hab ich jetzt auch gemacht, ob es was gebracht hat kann ich noch nicht sagen, da es ja nur bedingt auftritt...
Edit:
Ordner war ~900MB groß. Wurd vllt. mal höchste Zeit xD
Edit2: nope. Das war nicht die Lösung
Edit3:
Gerade festgestellt, dass das Problem auch bei Google Chrome auftritt
Edit4:
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