We ended up finding that the whole problem stems from emails getting rejected on our end because of a bad senders' domain. In fact, we're running into that a LOT. Never happened previously because we were running Exchange 2000. So, we're trying to figure out the best long term solution.