I had trouble with some verification emails not getting through. There was only one person I could ask to test it again and she did get one after I changed mail settings from PHP mail to SMTP and set up an SPF record. I ended up disabling verification emails anyway in the end.
I was having the exact same issues as mentioned in this forum and after much hair pulling I simply changed my Global Configuration - Mail Settings from PHP Mail Function to SMTP Server and left the SMTP Authentication set to NO.
It seems to work fine through Gmail and Hotmail accounts now. Both the user and Admin are receiving the confirmation mails.