We have followed the wiki instructions at:

https://docs.moodle.org/29/en/Office365

We have installed all of the office plugins on latest 2.9 branches.

And mostly things have seemed ok, but when we attempt to link a student moodle account to an Office account via the user profile we get a failure after the MS login page:

Sorry, but we’re having trouble signing you in.
We received a bad request.

Additional technical information:
Correlation ID: a34d9f2b-6423-4a07-ac37-51f524a41332
Timestamp: 2016-02-02 04:18:17Z
AADSTS90093: This operation can only be performed by an administrator. Sign out and sign in as an administrator or contact one of your organization's administrators.

The moodle log is a little vague:

local_o365\oauth2\token::instance: Cannot retrieve a token for the base resource. Data: (null)

The admin health checker says:

Moodle does not have a token to communicate with Office'365 as the system API user. This can usually be resolved by resetting the system API user.

However the System API user is setup and has a tick next to it, and that account is a full admin in the Office instance. We've tried a couple admins accounts and no luck. Resetting the System API user doesn't help.

I'm guessing it's just a missing permission on the Office side, even though it's an admin it could be missing something to perform actions on other accounts?? But perhaps it is even deeper than that, like when the System API user is linked in the moodle admin page it is either not retrieving the token properly, or not storing it properly for later?

Note we've also logged a support case with MS (paid account) but had fairly vanilla support so far.