The other day ran in to a problem with SMTP Routing via a Domino Server. The server was running 8.5.1 FP2. Off to search some technotes and work with IBM support and we identified SPR TPON83FH62
Regression in 8.5 SPR# TPON83FH62 – Fixed a problem in the Router where a failed message transfer to a destination host caused subsequent valid messages to be non delivered for the same reason. Typically this error is “SMTP Protocol Returned a Permanent Error”.
According to Technote 1424498 Subsequent outbound SMTP messages are rejected if one message has a permanent error this is fixed in 8.5.1 Fix Pack 3. Off to Fix Central and download and install of 8.5.1 Fix Pack 3. However after installing the problem still persisted, after further investigation it turns out that nrouter.exe was inadvertently left out of the fix pack. To see the files included in a Domino Fix Pack from a command line run the file name with a /CONTENT switch and you will see a box like this 
Been receiving DDM messages of this nature from all the 851 customers, but not seeing mail backup at any of them, but we also skipped 851fp2 due to other issues.
On unpatched 8.5.1 had several external SMTP domains for which we had to use a relay server. I assumed it was a blacklist on the server or router address but could easily have been this issue, since we’ve been able to go back to normal routing lately (FP3).
Hey Mitch, the fix did not make FP3. It is not fixed until 851FP4. A hotfix is availaible.