Delivery Delay, outgoing messages stuck in queue on Retry, MS SBS 2003

I have outgoing messages pending, going to 4 different external domains (SmallBusiness SMTP connector - domain.com (SMTP Connector)) . They've been sitting in the queue in a state of "Retry." One of them has been there for a day and a half.
Users who send these emails eventually get a message from Administrator saying:

This is an automatically generated Delivery Status Notification.
THIS IS A WARNING MESSAGE ONLY.
YOU DO NOT NEED TO RESEND YOUR MESSAGE.
Delivery to the following recipients has been delayed.

I've sent test messages to a couple other domains and they sent right away.

I ran the Exchange Troubleshooting Assistant: Mail Flow Troubleshooter, I got 2 warnings:
SMTP instance FQDN does not match DNS resolved server name
SMTP instance fully-qualified domain name does not match server name

I am not sure if it is related, or where and how to fix it if it is.
I looked at similar questions/solutions but didn't know how to apply them to my situation.
If it was just one recipient I'd probably dismiss it as their problem, but I have 4 at once.

Any ideas?