Apparently the mail server we use was incorrectly placed on a block list. This happened recently, and affected mail to some providers, like hotmail and MSN. It unfortunately meant some people couldn't register or change their passwords.
I've switched us to use a different email server and it seems to be working. Please let me know if you have any issues!
Also, this issue also affects Warcraft Mounts, but I haven't been able to find how to switch mail servers for that yet :/
Petopia mail server
Petopia mail server
Shaman avatar by Spiritbinder.