Thanks Gary! You are correct. Unfortunately, getting the right
people to believe you is the problem!
I am one contractor, the SMTP server is run by a different contractor,
and the liaison between us is handled by a third contractor. The
liaison here refused to believe the problem was on the SMTP server,
and assured me that it must be application-specific. So, basically, I
had to prove my innocence before the liaison would contact the SMTP
contractor. I eventually figured out to run telnet (with the proper
email port) on my Project Server application server and our SharePoint
Portal application server (where emails were working correctly). As
expected, the telnet succeeded from SPS, and failed from PS.