Codificación y robots

[sexto]

Hola que tal. Estoy teniendo un problema con una web.
La web se hizo hace como 10 años, y ha ido arrastrando ***** desde entonces, ahora yo he terminado de que funcione de manera más o menos decente, pero hay una cosa que no consigo.
La web tiene (y tenía) un buscador. Si yo busco una palabra con tilde, me busca en la BD correctamente y me muestra todos los resultados, incluso cuando se busca una palabra que tiene tilde pero se busca sin tilde.
Pero el problema viene por otro sitio: La web tiene una tabla de búsquedas, donde se van guardando todas las búsquedas que hace la gente y con un contador y tal. Después de corregir algunos fallos que tenía me he fijado en que muchas búsquedas se guardaban con una codificación muy rara, pero no es que sustituyera una tilde por un par de símbolos raros, sino una tilde por un montón de símbolos raros, por ejemplo:
Cursos de BÃ?Æ?Ã???Ã?? â?¬?¢Ã?Æ?â?¬Å¡Ã???Ã?¡sico de Productos Derivados a distancia en Asturias
Como no conseguía saber por qué pasaba, he puesto para que se guarde también la IP de la persona que busca, y resulta que en todos los casos que pasa eso, es el robot de Google o el de Bing.
¿Por qué pasa eso?
¿Hay alguna manera de evitarlo o solucionarlo?

Muchas gracias.