Symptoms
A customer сannot add domain to Office 365 in POA Control Panel due to the error message 'The domain(s) <domain name> cannot be used with Microsoft Office 365 because domain(s) have Mail Hosting enabled' like on the screenshot below:
Cause
Adding a domain to Office 365 service means that mail hosting on the domain will be served by the Microsoft Office 365 Cloud, however, a domain already has mail hosting configuredin POA using resource from another subscription.
It may be the same Office 365 service in another customer's subscription, it may be qmail or Exchange mail hosting service as well.
Resolution
Go to the list of customer domains hosted in POA in Customer CP - click the 'Hosted Domains' link on the 'Home' tab in CP.
Find the domain in question and check if it has mail hosting service configured already:

On the screenshot above it is seen, that the domain customer.org already has mail hosting confgured on it, so it cannot be added to the Office 365 service as these two mail services conflict with each other.
Control Panel does not show hosting on domains provided by APS applications, so customer has to analyze all APS applications installed in their subscription to check if the problem domain has mail hosting in an APS application, i.e. check if the problem domain is added to any application which provides mail hosting.
A customer has to decide what mail hosting service to keep on the domain - existing one or Office 365.
If customer wants to add the domain to Office 365 they first have to remove existing mail hosting from the domain and then add the domain to Office 365.