The reason the mail was not sent was revealed in the openerp server logs. Turns out OpenERP uses the user's ALIAS as the FROM SMTP header and that was not a valid user/email on that system. So I changed the aliases of the users to correspond to their email address and it now works.

Emails still don't show up in Settings > Email > Emails, so to find the error, you must look at the logs.