Hey, I have the same problem! I'm pretty sure it started with the latest update, 2020.36.3.1 or perhaps one update earlier.. I got two updates "back to back" only a few hours in between, must have been a quick bugfix or something.
I have Android 10 phone, Samsung Galaxy S7 running custom LineageOS. That obviously makes things worse, as people easily think that it's the custom ROM to blame. But Bluetooth worked fine earlier. I could sync my contacts and calendar, and answer calls and SMS viewed on screen etc. everything working.
Now, my phone says something like "can't connect because of invalid PIN", then requester pops up showing the new pin but it also fails. What's worse, these connection requests appear every two seconds or so, making the phone unusable because requester pops up so often. I have to disable bluetooth completely from my phone so I can use it.
I also tried to delete my phone from the Tesla's list, but it does not delete. Just stays there forever saying something like "removing device, please wait".. But it never finishes.
I also tried to first disable bluetooth in my phone, then reboot MCU with 2wheel-reset, this way making sure that it has never "seen" my phone.. But still can't delete the profile from the car.
I already thought this might be eMMC problem, but since you have the same issue I think it might be car firmware related after all?