Our exchange 2003 server stops receiving and sending e-mail at least once a day. The only way to make it work is shutting the server down and up again. We have tried all solutions listed on various sites, the most we have been able to go without disruptions is 4 days..then it's starts acting up again. It seems that SMTP protocol stops and then e-mail doesn't flow in or out even internally. Any solutions to this problem? We are on the verge of moving all mailboxed to another server. Please let me know!

Are you running Anti-Virus/E-mail filtering on the Exchange server? Is it producing error logs at the time SMTP goes belly up?

Not really. The only error we get related to SMTP is 2012 or 2013. We do have an antivirus running. It is ScanMail from Trend Micro. But we've had this antivirus running for more than 10 years with no problem. Any other suggestions?