Exchange 2003 emails not sending

Exchange 2003 running on SBS2003 was all going well for last 6 years until last week when users were finding outgoing emails taking around 2 hours to reach recipients. Then this escalated to them getting 'Deleyed delivery' messages and today they are unable to send out any email, with all messages returning after a while with "Delivery to the following recipients has been delayed". The first time a restart of the Exchange services seemed to work, although on attempting to dismount the Store, a c1041733 message was returned "The operation cannot be completed because a backup process of the targeted stores is currently running". Yet no backup was running. A re-start of the services fixed this, which may or may not have been related to the delayed delivery issue. It could just as easily be an unrelated and insignificant issue. But today, several re-starts of the Services and a full server re-boot have failed to resolve the issue, as has a temporary disable of the AVG Security software. The outgoing mail is stacking up in c:\program files\Exchsrvr\Mailroot\VSI 1\queue. I can't see this being a DNS issue as nothing has changed from when it was working ok. Incoming mail through the pop connector is fine. Users can send email ok from all workstations and from the server via pop/smtp mail accounts but not Exchange. In Event Viewer Application Log there are once per hour or so error id 2013 source smtpsvc "SMTP could not connect to any DNS server. Either none are configured or all are down". Looking back, these entries started appearing on 16 August..... but emails were going out 100% ok from then until last week when the delays started.