email verifications not being received

This should be so simple ... We've invited several people we know to join our community website. Half of them are not getting the verification email after registering but half of them are. So a lot of people cannot login because their membership never gets activated.

All sorts of browsers, operating systems, email clients so I don't see any kind of pattern here. My wife and I both use MSN and I can get the email but she doesn't (tried 3 times now).

On one of my single sites, I have a menu item under Users > Unverified Users but I don't see that in my network multi-site admin. That's where I can verify a user manually if I want to. Is this a multi-site thing or maybe I'm using a theme that has that special feature?

Any ideas?
Thanks in advance.