Yes, PoliteMail works with Office 365 Hosted Exchange

PoliteMail Server will require an Exchange Service Account, with adequate permission levels to request members of the distribution groups you intend to send to.

Please note, PoliteMail for Outlook requires the desktop version of Outlook, and will not work with Outlook online.

Configuring PoliteMail Server for Office 365, and Office 365 Hybrid, and Office 365 Dedicated solutions may require specific configuration settings, depending upon your specific implementation details.
These configurations are handled on a case by case basis by your assigned PoliteMail Server Administrator.

Office 365 Dedicated solutions require that the PoliteMail Server system be configured to communicate with Exchange, in other words, your Exchange Service must be visible to the PoliteMail Server over your network. PoliteMail Enterprise Cloud Servers may be deployed using a virtual private cloud architecture to support IPsec connections.

In Hybrid deployments in particular, using EWS to access your AD often need to occur on the internal Exchange Server and not the Office 365 Server returned by autodiscover (as of June 13, this issue is planned to be resolved by Microsoft, and this article will be updated once this changes).