[0peceric0]

La busqueda de google está integrada en el launcher, por tanto no puedes deshabilitarla ni desinstalarla, prueba a borrar datos antes de nada.

Edito:
No te había leido bien, si ya has restaurado de fábrica y sigue igual entonces ni idea.