Gmail API suddenly stopped working with [Error: unauthorized_client]

Where I work we use Google Apps for Work. For the last 9 months we've been using the Gmail API (~2,000 requests per day) to pull in new emails for our support email accounts.

This is how we originally set it up:

1. Go to https://console.developers.google.com/project/
2. Click on the project (or create a new one)
3. Click on API's & Auth
4. Click on Credentials
5. Click on Create new Client ID
6. Click on Service account
7. Download a JWT (json) for the account.
8. Follow the node.js quickstart guide with an installed/native type token for the same account, and authorize it through the console. The JWT tokens did not work unless we did this step, once for each account.

We did this for each of our individual support email accounts to avoid having to turn on domain wide delegation for any of them in the admin console. We were then able to authenticate with the tokens using the officially supported npm library googleapis, similar to this:

var google = require('googleapis');

var jwtClient = new google.auth.JWT(
    token.client_email,
    null,
    token.private_key,
    ['https://www.googleapis.com/auth/gmail.readonly'],
    '[email protected]'
);

jwtClient.authorize(function(err, tokens) {
    if (err) {
        return cb(err);
    }

    var gmail = google.gmail('v1');
    var requestOptions = {
        auth: jwtClient,
        userId: 'me',
        id: messageId,
        format: 'raw'
    };

    gmail.users.messages.get(requestOptions, function(err, response) {
        if (err) {
            return cb(err);
        }
        // do stuff with the response
    });
});

Like I said, we used this for a long time and never had any issues. Yesterday around 10am MST every one of the accounts stopped being able to authenticate at the same time, with jwtClient.authorize() suddenly returning the error [Error: unauthorized_client].

I tried doing the same thing with a new token on a new service account (the web interface to get the token has changed quite a bit in the last 9 months), and it returns the same error.

The version of googleapis that we were using was 0.9.7, but we can't get JWT authentication to work on the newest version either.

We opened a ticket with the Google APIs support team, but the support person we spoke with had never read the Gmail API specs before and was ultimately unable to help us, so he redirected us here in order to get in touch with the API engineering support team.

We have noticed that authentication works if we enable the scope for domain wide delegation in the admin console, but we would prefer not to do that. We don't need to impersonate the accounts and would prefer to use an individual JWT for each account.