Error 500 logging into ADO or Private Nuget feed

I have a long standing user who in the middle of last week lost his ability to login got ADO or connect to our private feeds getting an 500 Internal Server Error. The situation is complicated slightly in that we share an ADO Subscription amongst multiple tenants so this use is added as an ExternalAzureAD Guest.

I dropped and recreated the user both in ADO and his guest account in the ADO joined tenant, waited half an hour and then re-added the user with to ADO, but still the same error. I have done the same with a scratch user and all this works without issue.

When the user goes direct to the private feed and logs in, they get the error:
{"$id":"1","innerException":null,"message":"TF400813: The user '66faf51b-bf86-6913-bd44-d1b38246c0ea' is not authorized to access this resource.","typeName":"Microsoft.TeamFoundation.Framework.Server.UnauthorizedRequestException, Microsoft.TeamFoundation.Framework.Server","typeKey":"UnauthorizedRequestException","errorCode":0,"eventId":3000}

When they try to login to ADO, the get the attached error:

We tried this on a different machine and got the same behaviour, so it seems account related.

How can I resolve this?