This is another example of how different Exchange 2003 is to set up versus 5.5.
As I have written before, I have two Exchange 2003 servers, one back-end server, where all the mailboxes and public folders are primarily stored and one front-end server that handles SMTP traffic, bridgehead and routing functions, OWA, replication with the 5.5 server and a few other things. The front-end server has the default SMTP virtual server and the Internet Mail SMTP Connector (Exchange 2003 version of the 5.5 IMS or Internet Mail Service). All outgoing mail from our organization goes through the Internet Mail Connector to our ISP's email relay, which is usually done to hide the internal server, but since our ISP's gateway doesn't strip off the header information of relayed SMTP emails, it's just there to offload some work from the front-end I suppose.
The problem that I ran into was that replication and other traffic going from the front-end to the back-end was getting stuck in a queue on the front-end. Everything seemed to be working OK, so I put the problem on the backburner after poking around initially.
Then I had a problem with one of the Public folders that receives email from the internet. It wasn't getting mail that it should have gotten. I finally noticed that the mail was stuck in the aforementioned queue. So I had to resolve the problem right away.
As I was poking around, I noticed that I had set the SMTP virtual server to also forward all email to our ISP's gateway. So the mail was getting stuck in the SMTP virtual server's queue because it was attempting to send to the ISP's SMTP server and that server did not recognize the domain name at all and was basically rejecting the mail. So I set the SMTP virtual server so that it would route emails as necessary instead of forwarding everything to the "smart host" and that resolved the issue.
So at least anyone who cares to search for a similar problem can come here and make sure they haven't made the same mistake. I know I won't be making that one again. :)