Exchange Server 2000 Enterprise Edition

We have recently upgraded to the Enterprise Edition to support more than the 16GB limit on the database. Ever since we have done this we receive mail - no problem, but the outgoing SMTP mail sits in the queue "messages with an unreachable destination", but after restarting the SMTP service the mail transfers to the "email (SMTP connector - remote delivery)" queue and eventually gets sent out. Any ideas what could be causing this. Our router settings have not changed, nor have our ISDN lines (x2).