This, however, has not even put a dent in our problem. Still well over 14,000 messages that cannot be sent.
I have stopped... started... restarted... flushed... wiped... washed my hands... wait where was I.... oh yes... mail server....
Any other suggestions on this?
Also... does anyone know anything about postfix's directory structure. We have all the messages sitting in /var/spool/mqueue. /var/spool/postfix/active, incoming, defer, and deferred are all empty (save for other directories).
Thanks to those of you who posted regarding MTU path discovery. It sounded like that was indeed our problem.
Thanks again for the help.