How do I need to configure SMTP Auth?
Most providers block smtp ports, I had to use a mail redirection service when I set this up.

If the message gets through after 15 minutes though, I suspect you have a  mail server misconfiguration. Nowadays, I usually go for a much simpler approach, I use google's smtp server to send the emails.

An easy way you can test if port 25 is blocked is by connecting by SSH to a remote server, then trying to telnet on local server port 25. 

telnet mail.port25.com 25


If the port is open, you should get a response similar to this:

Trying 69.63.149.30...
Connected to mail.port25.com (69.63.149.30).
Escape character is '^]'.
220 mail.port25.com (PowerMTA(TM) v4.0) ESMTP service ready


Another thing to check, if you are using qmail make sure the trigger file has proper permissions. qmail/queue/lock/trigger should be prw--w--w qmails:qmail.