domh
>...the remote queue had about 80+ messages in it.
What makes you think that that is a problem ?
Are all of your outgoing messages not getting delivered or only some ?
Qmail will keep trying to deliver a message for 7 days, so it will stay in the queue for that long, before qmail gives up completely.
The log messages are probably telling you the problem, ie that your server could not establish a smtp connection with the server that is is trying to deliver a message to.
Theoretically on a busy server you could have hundreds (or even more) messages in the remote queue that cannot be delivered to other servers for a variety of reasons.
If the dates on any of those messages are older than 7 days then you do have a problem, but for 7 days qmail will keep retrying to deliver the messages, and then finally give up.