Vilken version av Internet Explorer har du? 6, 7, eller 8?
Hur funkar det om du kör med IE och använder google som din startsida? Får du samma meddelande då också när du söker?
Eftersom du har scannat efter virus och spyboots så verkar problemet inte ligga där?