I have seen this bug before.
It seems to be because the email sent is malformed. On many mailservers, it's OK. But on others, it's blocked.
Tiki uses 2 different libraries to send email. The one used for the newsletter works fine whereas the the one for "e-mail verification" doesn't work on some servers.
I will check if I can dig up something...