Exchange Internet Email problem

I’m running Exchange 5.5 SP3 on an NT 4.0 SP6a server. I’m having problems with the Internet Mail connector “breaking” overnight. I’m wondering if it is backup-related: we use Veritas’ Backup Exec (latest version) on the same server, which backs up to tape every night. When I come in to check in the morning, mail is often down. Simply stopping and restarting the internet mail service brings it back up. Anyone care to try answering this one?