To answer my own question, it seems that there was a proxy address added to these users, in the form of smtp:@mydomain.com in addition to the smtp:@mydomain.onmicrosoft.com.
You can only? remove this with the Microsoft Graph explorer by running a query:
PATCH https://graph.microsoft.com/beta/users/<object_id_user>/
{
"proxyAddresses": ["smtp:******@mydomain.onmicrosoft.com"]
}
After that the domain can be removed