Using SMTO_BLOCK seems to have fixed the problem. Although it was hard to duplicate the problem a lot, since it is all timing dependant, so I'm not 100% sure. In any case, it makes sense that this fixed it, as SMTO_BLOCK does not allow other sent messages to be processing durin the duration of the SendMessageTimeout call, which should fix the problem being experienced.

Thanks for pointing in the right direction.