Another detail, which may or may not be relevant: what is your value
   of mail-user-agent?

mail-user-agent is a variable defined in ‘simple.el’.
Its value is ‘sendmail-user-agent’