Does not send E-mail to admin or user

(I have searched for 2 days trying to find out more info and I have tried other people's solutions for similar problems but to no avail.)

I do not receive an E-mail when a new user registers, neither does the user.
Playing with send mail by role or custom email does not seem to make a difference.
I cannot debug, because when a user completes the registration there is no debug information, they are taken straight to my home page without any kind of message.
The database is updated correctly, but no emails are mailed.

I am using SMTP authentication. Test E-mails on this work.
All of my contact forms work.
Request new passwords work.
If I manually process the new user they receive the login email and password no problem.

It is getting to me, as this is the final part of the system in testing before we launch our new site. I am almost at the point of switching it all off, but we would really like the participation.

I know many people have had similar issues but their fixes don't work for me, can anybody help?
Paul