FWIW, Some notes from a colleague who has been working on this and it seems to work.
MAS 90/200 Paperless Email for Office 365 users:
Setup the IIS using the following instructions:
http://support.microsoft.com/kb/2600912
Then, in MAS90 e-mail setup:
Setup mail to send to your local server
Use your server name and port 25
Use your local domain credentials
MAS90 then sends the unencrypted mail to your local IIS server which encrypts with TLS and forwards to the Office 365 server.
The Office 365 mail account you enter in the IIS settings needs to be the same one that you send from (your reply address in MAS90 setup for paperless office). To avoid having to set up multiple Office 365 mail accounts, you can have all outbound mail from Paperless come from a single user.
For Exchange 2010
We have had some problems sending via Exchange 2010 and this may be related to TLS as well. There is a setting in the Relay Connector for Exchange 2010 that may need to have Basic Authentication checked and not TLS.
See http://exchangeserverpro.com/how-to-configure-a-relay-connector-for-exchange-server-2010