Exchange 2000 outbound mail

I have an Exchange 2000 server that is having problems sending mail to a specific domain. Messages will continue to queue for that doamin but will not send until I stop and start the virtual smtp server. This is happening for the one domain only. If I let the queue sit, users will get an undeliverable after the 2 day time out.

I logged the smtp traffic via exchange and the message did not attempt until the stmp queue was set to shutdown, 45 minutes after the message was originally queued. Additionally, I am able to telnet to port 25 from the exchange server to the remote domain and manually send a message without failure.

Any ideas why this would happen for just one domain and how to fix it?