3
Agreed, let us know what email option you have chosen and what results you get. Create test accounts (test1, test2 test3 etc) to see what results you get for each option. php() mail should work in most cases, but if that fails try sendmail. Check with your host for the sendmail path, but the default should be enough for your needs.
If it's imperitive that your users get registered right away, I suggest allowing automated authentications until you get this resolved, then moving over to the verification method. Once you are sure email verifications are working, you change back.