Due to an internal AWS issue the UID mechanism was failing for some of the requests with a UID set (only US region affected). We had an issue with our fail-safe mechanism which was causing it to return 500 errors even though the messages were correctly processed and sent.