If you are using Domino 8.5.1 and SMTP gateway, do not miss to install FP3.
There is a know issue, In Lotus Domino 8.5.1 when one SMTP outbound message is rejected with a permanent error, such as "user not known", subsequent messages queued for the same destination are also rejected.
You receive delivery failure reports for messages where the failure reason is "Permanent error" with no supporting information.
This issue is now fixed in Lotus Notes and Domino 8.5.1 FP3 and 8.5.2.
Fix details: SPR# TPON83FH62
Refer the IBM Technote for details.