jcreed - thanks for posting the solution to your problem with xp_sendmail (which is the same problem that I had a few months ago and fixed with the same methods that you did) - however, there is an intermittent problem and a steady problem with xp_sendmail.
Anu - If your problem is every x days then I would pursue the listing by jcreed; otherwise, let me know.
xp_sendmail: failed with mail error 0x80004005
I had the same problem a while ago after System Administartor added NT login restriction on the SQL 2000 server. This has been resolved by stop and restart the services of SQLSERVERAGENT and MSSQLSERVER. I do not know if this is the case for you but it worked with me. So try it if this happens again.