Gracias por vuestra ayuda, al final la culpa no era de la ROM ni de Gmail, sino más bien del funcionamiento propio del Real Mail, que se asemeja bastante a una patata.
Por si alguien tuviera el mismo problema, siguiendo vuestros consejos, lo que he hecho finalmente es lo siguiente:
1-. Configurar mediante web mi cuenta de Gmail en la pág
http://push.vodafone.es
2-. Acceder a tu bandeja de entrada desde esa misma página y borrar TODOS los emails. De esa manera liberas el espacio del servidor y Real Mail no se vuelve loco (no te preocupes, los mensajes borrados seguirán estando en el servidor de Gmail). Si tienes miles de emails puede ser una ardua tarea: yo utilicé una macro para no perder demasiado tiempo dando millones de clics y esperando a que se cargara la página cientos de veces.
3-. Después instalas el .cab del Real Mail e inicias el programa. A partir de ahora, sólo los mensajes nuevos aparecerán en tu móvil, y no la basura que te mostraba antes.
Salu2!