Postfix Relay to Office365
Just in case anyone comes across this later. I DID finally get a proper email relay working. The issues had to do with using an older version of postfix, which formatted the "FROM" element in the envelope in a way that Office 365 didn't like. Updating Postfix to 2.9 or greater (and using a config like the one above) solved the issue.
Solution:
Don't send mail to Office365 as a user from your Office365-hosted e-mail domain. Use a subdomain instead, e.g. [email protected] instead of [email protected]. It wouldn't hurt to set up an SPF record for services.mydomain.com or whatever you decide to use.
Don't authenticate against mail.messaging.microsoft.com as an Office365 user. Just connect on port 25 and deliver the mail to your domain as any foreign SMTP agent would do.