My Exchange server is behind a Linux firewall with sendmail fronting the email handling. I started seeing messages in the maillog on the Linux machine like:
dsn=4.0.0, stat=Deferred: Connection reset by <em>mailserver</em>.

Following that were even odder messages from SpamAssassin:

This was all due to the added security of the Exchange Server installation (I believe it is also true for 2007). It is set up for authenticated connections and to disallow anonymous connections.

To resolve, I added a new Receive Connector in the Exchange Management Console for my sendmail front end machine under Hub Transport in the Server Configuration. I set this up to only receive mail from the IP Address for my sendmail machine and checked the Anonymous users permission group. Adding this new Receive Connector allowed email to be received from my sendmail machine once again.

In simpler terms:

1. Open Exchange Management Console
2. Click on Hub Transport under Server Configuration
3. Click on the corresponding hub in the top section
4. Right-click on the bottom section and add New Receive Connector
5. Using Custom as the intended use:
   1. Listen on Port 25
   2. Enter the desired FQDN
   3. Edit the IP Range to match the address of the sendmail machine
   4. Create the New Receive Connector
6. After the Receive Connector is created, right-click on it and select Properties
7. On the Permission Groups Properties tab, select Anonymous users and press OK

A working system!