The issue occurs when EXM tries to send multiple automated emails at the same time. If the same message is triggered multiple times in a short period of time, only one message is sent. The EXM log shows messages as follows:
ManagedPoolThread #12 16:07:59 DEBUG Job Sending message ([Job_ID]) already running. Not started.