Office 365 uses "https://outlook.office365.com/EWS/Exchange.asmx" as the Exchange Web Services (EWS) URL.


The next release (in about 3 weeks) will have AutoDiscovery features built in.  This will help a lot in resolving these types of questions but only if the users Exchange platform is configured to use EWS or a user is on Office 365 as you are.