So it seems Google forgot to include this little detail in their documentation:
AssertionFlowClient provider = new AssertionFlowClient(server, certificate)
{
ServiceAccountId = SERVICE_ACCOUNT_EMAIL,
Scope = "https://mail.google.com/",
ServiceAccountUser = "user@mydomain.com", // <- important
};
It also seems that requesting access to multiple scopes (space separated) fails.