OK. Problem solved. The problem was caused by the multitude of hostnames associated with the external IP addresses serviced by this firewall. One of the names was the mail server's name, so sendmail thought it was the mail server. I decided to add dummy entries into the /etc/hosts file, so that upgrades would be less complicated.
(Un)fortunately now I know more about sendmail than I ever wanted to, but not enough to truly be competent. (Does anyone outside of a mental institution understand the gobbled-goop in a .cf file?!?) It really is too bad that the other secure mailers have incompatible licenses. *SIGH*
