Caracteres extraños

[javifo]

Hola a todos.
Tengo un problema al que no encuentro la solución.
La web está en PHP y a parece indexada en Google y MSN.
El problema es el siguiente:

1.- El título de la página se genera dinámicamente con
<title><?php echo $titulo; ?></title>. Se recoge de la BD y hasta aquí no hay problemas. Aparece bien en los navegadores.

2.- Si desde el navegador se mira el código fuente, el título aparece correctamente escrito.

3.- Cuando Google o MSN indexa la página aparecen los problemas. Lo que pasa es que si el título contiene un acento o cualquier caracter extraño (una ñ, por ejemplo), Google y MSN indexan la página con un título que contiene caracteres raros.

Por ejemplo: Si el título es Dirección Comercial, aparece Dirección Comercial.
Si es Técnicas de Venta, aparece Técnicas de Venta. Este es un ejemplo tomado de MSN. Google indexó estos títulos de forma parecida, pero ahora aparece la página indexada sin título.

La cuestión es que si no encuentro solución, las palabra que contengan un acento nunca darán resultados en las búsquedas.

Hay algo que no entiendo de los robots y es que si la página se muestra bien en los navegadores, imagino que es que está bien construida (incluso el título)
y no comprendo cómo Google y MSN interpretan el título de forma tan distinta.

Os agradecería mucho vuestras opiniones y soluciones.

Muchas gracias.