When you say still no luck, do you mean sendmail is not running or the queue is not being emptied. Do "ps -ef | grep sendmail" to see if it is running. If not, check syslog for error messages. If it is running, it might be a problem with dns. If you run your own nameserver then stop and restart...