So where do we start? Here are a few things you can do to validate whether they are sending or not.
1. Create a test account at your site using a 3rd party email provider like GMAIL and see if you get the confirmation email. There could be a possibility that they are going to a user's spam folder instead of the inbox.
2. Are users getting ANY notifications via email from your site? (comments, friend requests, etc)
3. Are you using your own server to send emails or using the SMTP module?