REST API - Update user - Email Address Already Exists

I have been using the REST API /api.ashx/v2/users/{userid}.xml to disable users who leave the company in an automated script against our 8.5 community for years. As part of that disable I remove values for a number of profile fields and change the email address from a "friendly" address, which could be reused, to their, which I know will always be unique. I am setting both PrivateEmail and _ProfileFields_Email to this value.

This past weekend we upgraded to 10.1.6. Now for some users (20-30%) that are being disapproved the API returns: 

<Message>A user with this email address already exists.</Message>

If you search for the email address I am trying to change the user to in the Administration > Members panel that address is not found.

I have searched in the cs_Users table in the DB and I cannot find any instance of that email address in use.

I have also looked in the the other User tables; cs_UserProfile, aspnet_Users and aspnet_Profile. I don't see any use of the email address in any of those tables either. 

I am at a loss to figure out where that email address is in use, or why these users are different from those where the account is disabled "normally". 

I have tried changing the email address in the Administration > Members panel and I get the same error.

I can change the email address to add an extra character to their "UserName" and that works, both via the Administration > Members panel and by the REST API. After that I can change the email address to what I want it to be set to just fine, both in the Administration > Members panel or using the REST API.

Can someone offer some insight into where this email address is in use and why only some users are affected by this?