Hi Did you find a solution to your problem. I am having the exact same problem. I am a newbie to SQL server 2008, but I did configure it to work the first time. After SP 1 2008 for sql server, I subsequently ran into problems and had to create a new instance. I have tried all possible settings in Database mail configuration utility. In parameters i increased the time out period, but still no luck

The error message in the log file

The mail could not be sent to the recipients because of the mail server failure. (Sending Mail using Account 2 (2009-04-30T12:25:17). Exception Message: Cannot send mails to mail server. (The operation has timed out.)

I have configured sql server agent to use my database mail profile.