Question : Exchange 2003 outbound messages in queue for several days

Several messages to a couple of locations have been in queue for several days. The only thing I see is under additional queue information: An SMTP protocol error occurred

Answer : Exchange 2003 outbound messages in queue for several days

You would ask your ISP for an rDNS entry.

That the problem has mysteriously disappeared is the concerning part - I don't know what the cause was...