Did you check to see if they installed any browser plugin? (run hijackthis)
Or, activex: (Tools, internet options, programs, manage addons)
Does it happen only with the built in search bar?
Does...