Dan,

I am going to answer your second question first. STARTTLS requires an SSL cert and therefore, it will alway be there. However, I have a feeling option# 2 on Microsoft's site is only applicable if you're trying to relay from another Exchange server. If this assumption is correct, the only option you have is option# 1.

I want to understand your deployment scenario a bit better before going any further. Could you please confirm the following network diagram is correct?

Web Server -- > Xeams --> Office 365 --> FinalRecipient

Consider the following as an example email:

From: john@OneOfYourClient.com
To: mary@gmail.com
Subject: Testing

John is hosting www.oneofyourclient.com on your network. His web server sends emails to someone at gmail.com when they sign up for some service. John's email is not hosted by you. Instead, it is hosted by Microsoft's Office 365.

Is this scenario correct? If it is correct, why are you trying to relay the messages via Office 365? When not let Xeams send this message directly to gmail.com?