Eso es porque hay cuentas que no son compatibles con este tipo de mensajes. Te puede pasar perfectamente con una cuenta Hotmail, por ejemplo.
Para evitarlo yo me hice una cuenta también en Gmail y para cualquier registro uso siempre esa. Así sabes que no hay problema con los correos que te tengan que llegar. Y este tipo de cuentas, yo por ejemplo tengo de Orange y Orangemail (que no reciben prácticamente ningún correo de verificación o las de Hotmail (que no recibe bastantes), las dejo solo para uso personal
