@Sweetspotter did you try the method @Vanlife4me mentioned. This is not the normal "contact support" response we get from EA, it has actually consistently worked for people including myself.
ACTUAL SOLUTION:
I had the same problem. Fully explained in this thread verified by EA AHQ staff, online support is useless and cant help.
https://answers.ea.com/t5/EA-General-Questions/Unlinking-Dormant-deleted-Account-from-Xbox-without-o...
Basically you need to contact EA's Data Protection Officer (Links and explanation in thread linked above). From there they will verify you via Xbox live by sending you a message from their test machine with a verification code, you email it back and they then reset the account unlinking it from your Xbox account, allowing you free to add a new one. No reason it wont work for your Microsoft account so long as you have access to that.
Took me 2 days to get an email response then it was sorted within a couple of hours.
I did this literally couple days ago and now spreading it on here so the EA staff here know about it, and the community starts to pick up on it. Solution was tick as solution on the thread.
As long as you have access to the Xbox or PSN account this method works, but for some reason EA is not pushing it.