Hi,
I had a similar problem with MPE. I can not rember the version I installed initially, but e-mails didn't go out to the users. The status report messages were the same as you had.
I reinstalled this version but this didn't solve the problem, then I installed version 1.2.1.1 and e-mails were send out correctly.
I didn't have the Exchange license, the configuration was just pointing to an SMTP server.
To me it looked that there was an SMTP bug in my "old" version.
Sorry, I don't recall the exact version of MPE that had this problem.
Jan