This particular customer was routing through a smart host for spam protection. They cancelled their spam protection so I went in to the ECM and checked Use domain name system (DNS) "MX" records to route mail automatically instead of "Route mail through the following smart hosts".
Seemed simple enough so I sent myself an email from one of their workstations to test it. It seems to be stuck in the queue with an error 451.4.4.
Any idea what I missed?