Should they then request a 'lost password' they receive the lost password email
I don't see how this can be an SMTP issue
It was just something to check as part of troubleshooting. You receive admin mail so mail is configured correctly. But other people do not receive mail which makes me think it could be a SMTP relay issue.
But if they can receive lost password emails then that's probably not it. But looking at the mail log would at least confirm if your installation is even attempting to send that mail.
Do you have any plugins activated on your installation? Just as a temporary measure can you deactivate all of them and switch to the Twenty Eleven theme? Then have someone else (or use a different browser with it's cookies cleared) attempt to register again.