If you google this error, you will find out that there are a whole bunch of reasons why this error happens. The only way to find out why it gives that error is by going into the transport logs for your frontend. 

If you use custom internal relays then you need to set the Protocol logging level to Verbose. By default all the custom relays you make have it set to None. 
You can do this by going to the Exchange ECP > Mail Flow > Recieve Connectors > open the properties of the relay connector > General section

The logs can be found in C:\Program Files\Microsoft\Exchange Server\V15\TransportRoles\Logs\FrontEnd\ProtocolLog\SmtpReceive

In my case the following error could be found:
message or connection acked with status retry and response 451 4.4.395 target host responded with error. -> 454 4.7.0 temporary authentication failure

The fix was to set the time correct on the domain controllers, one of them was 10 minutes ahead for some reason. After correcting the error, it took about a minute or 10 before the mails started flowing back in again.