1) Check that your smtp server is setup in Central Admin > Outgoign email settings. Verify BOTH the farm and web application settings.
1a) Check the FROM address has been set.
2) verify the users have the correct SMTP address
3) Use SMTPTest Tool / Telnet to send a test email to the same SMTP server in 1 using an address from 2)
I konw you've said you've done this but you've likely missed something - http://sharepointalert.info/troubleshooting-sharepoint-alerts/