Gracias a todos por los consejos!!
Al final, llegamos a la conclusión de que Windows Mobile + Movistar + Mi casa = Muerte con ojos.
Digo Windows Mobile porque mi hermano tiene un Omnia y le pasaba lo mismo... pero al final dejó de hacerlo y funciona con normalidad, así que no fue fallo del cacharrillo afortunadamente!!!!
Saludos!