I'm pretty sure I've noticed the same thing before - the send email APIs (both SS1.0 and SS2.x) don't seem to trigger UEs on the Message record, at least reliably. To solve for that, I've got whatever function/processing that's running in the Message record's UE also being called separately with the relevant
nlapiSendEmail()
/
email.send()
calls.