I have experienced this problem before. If you have checked everything and all is well, then the problem is most likely because the mail() function included with stock PHP does not support SMTP authentication.
I eventually had to use the PEAR Mail package which is much more comprehensive and supports outgoing mail server authentication.
A quick google search reports the following example: