I have so much difficulty sending authentication mail to new user that I'm considering relying only on third party logging system like stackoverflow does.
The problem is that contrary to this site, my website is targeted to a not so tech-savy audience.
So two questions arise:
What are the solution to get a rock solid email delivery solution to stop losing new costumer and fix my system? (a lost around 50% of them as I write)
Would you just stop serving identification and rely solely on a third party service if your audience was not so tech-savy?
Perhaps you should start with finding out why your e-mails are lost or tagged as spam? If you're sending reasonable content from a properly configured, non-blacklisted mail-server, there is absolutely no reason for 50% of your mails to get lost.
Your best option is probably to send a mail to an account, which provides a detailed output from the spam check software and solve each of the issues or rules your mail is violating. If that's not possible, you should check if your mail server is blacklisted (as Jonas suggested), your server configuration (your mail server may HELO with an incorrect host name), the format of the mail message itself (your software may produce an incorrectly formatted message), the content of the message (is the wording similar to common spam or phishing mails) and if you are included unneccessary file attachments. Without more details, it is however not possible to be more specific.