Have you tried using another browser? There's a Trojan going around that, as I understand, cripples the browsers' search functions. But it effects all the browsers on the computer. And, as I recall, the symptoms are slightly different.
Unfortunately, I just read about it in passing when looking up something completely different, so I don't remember much about it and I just tried a quick Google and came up with nothing. But if it seems like it could be the potential problem (i.e. IE doesn't work.) then you should look into it.