Running evolution with CAMEL_DEBUG=all showed this when sending a message that fails:

Thread 0 >
CamelFolder:get_message('Outbox', '54') =
class: CamelMimeMessage
mime-type: multipart/alternative; boundary="=-CBXr31lPJYljaUmG6Vyf"
content class: CamelMultipart
content mime-type: multipart/alternative; boundary="=-CBXr31lPJYljaUmG6Vyf"
  class: CamelMimePart
  mime-type: text/plain; charset="ISO-8859-1"
  content class: CamelDataWrapper
  content mime-type: text/plain; charset="ISO-8859-1"
  class: CamelMimePart
  mime-type: text/html; charset="utf-8"
  content class: CamelDataWrapper
  content mime-type: text/html; charset="utf-8"
< 0 >
Thread 0 >
CamelStore('mapi://<email address hidden>/;sync_offline;profile=username@DOMAIN;domain=DOMAIN;command=ssh%20-C%20-l%20%25u%20%25h%20exec%20/usr/sbin/imapd;check_all;filter'):get_folder('Mailbox - Andre Scandaroli/Caixa de entrada', 0) = 0xb6b97820
< 0 >
Event : Message created
	Folder Entry ID: 0x2d5890000000000a
	Message Entry ID: 0xcd882c000000003b
	 Tag: PR_HASATTACH
	 Tag: PR_TRUST_SENDER
	 Tag: PR_SEARCH_KEY
	 Tag: PR_LOCALE_ID
	 Tag: PR_MESSAGE_LOCALE_ID
	 Tag: PR_CREATION_TIME
	 Tag: PR_LAST_MODIFICATION_TIME
	 Tag: PR_LOCAL_COMMIT_TIME
	 Tag: PR_INTERNET_CPID
	 Tag: PR_SUBJECT_UNICODE
	 Tag: PR_SUBJECT_PREFIX_UNICODE
	 Tag: PR_NORMALIZED_SUBJECT_UNICODE
	 Tag: PR_SEND_RICH_INFO
	 Tag: PR_MESSAGE_FLAGS
	 Tag: PR_INTERNET_REFERENCES
	 Tag: PR_IN_REPLY_TO_ID
	 Tag: PR_INTERNET_MESSAGE_ID
	 Tag: PR_BODY_UNICODE
	 Tag: PR_RTF_COMPRESSED
	 Tag: PR_HTML
	 Tag: PR_MESSAGE_SIZE
	 Tag: PR_RTF_IN_SYNC
	 Tag: PR_MESSAGE_CODEPAGE
	 Tag: PR_CLIENT_SUBMIT_TIME
	 Tag: PR_MESSAGE_DELIVERY_TIME
	 Tag: PR_INTERNET_ARTICLE_NUMBER
Event : Message deleted
	Folder Entry ID: 0x2d5890000000000a
	Message Entry ID: 0xcd882c000000003b
Event : Message modified
	Folder Entry ID: 0x2d5890000000000a
	Message Entry ID: 0xcd882c000000003b
	 Tag: PR_HASATTACH
	 Tag: PR_TRUST_SENDER
	 Tag: PR_SEARCH_KEY
	 Tag: PR_LOCALE_ID
	 Tag: PR_MESSAGE_LOCALE_ID
	 Tag: PR_CREATION_TIME
	 Tag: PR_LAST_MODIFICATION_TIME
	 Tag: PR_LOCAL_COMMIT_TIME
	 Tag: PR_INTERNET_CPID
	 Tag: PR_SUBJECT_UNICODE
	 Tag: PR_SUBJECT_PREFIX_UNICODE
	 Tag: PR_NORMALIZED_SUBJECT_UNICODE
	 Tag: PR_SEND_RICH_INFO
	 Tag: PR_MESSAGE_FLAGS
	 Tag: PR_INTERNET_REFERENCES
	 Tag: PR_IN_REPLY_TO_ID
	 Tag: PR_INTERNET_MESSAGE_ID
	 Tag: PR_BODY_UNICODE
	 Tag: PR_RTF_COMPRESSED
	 Tag: PR_HTML
	 Tag: PR_MESSAGE_SIZE
	 Tag: PR_RTF_IN_SYNC
	 Tag: PR_MESSAGE_CODEPAGE
	 Tag: PR_CLIENT_SUBMIT_TIME
	 Tag: PR_MESSAGE_DELIVERY_TIME
	 Tag: PR_INTERNET_ARTICLE_NUMBER
Event : Message moved
	Folder Entry ID: 0x2d5890000000000a
	Message Entry ID: 0xcd882c000000003b
	Old Parent Folder Entry ID: 0x9cf65200000001a
	Old Message Entry ID: 0x0
Event : Message copied
	Folder Entry ID: 0x2d5890000000000a
	Message Entry ID: 0xcd882c000000003b
	Old Parent Folder Entry ID: 0x9cf65200000001a
	Old Message Entry ID: 0x0
Event : Message created
	Folder Entry ID: 0x2d5890000000000a
	Message Entry ID: 0xcd882c000000003b
CamelException.setv(0xb218d0c0, 303, 'Could not send message.')

Nothing special with the message. Sending the same message using another evolution account that has only the SMTP pointing to the exchange server worked.

I wonder if evolution-mapi plugin uses SMTP to send out e-mails. There is no option for configuring this in the account settings dialogs.