Try completely unpairing and re-pairing the phone and car. On the car side, delete the phone as a key and also open the Bluetooth menu and tell the car to "forget" the phone. On the phone, open the Bluetooth menu and tell the phone to "forget" the car. Also, for good measure, delete the Tesla app on the phone. After that's done, reboot both the phone and the car (this may be unnecessary; I'm just trying to suggest everything that even
might be helpful), re-load the Tesla app and log back into your account. Then re-pair the phone as a Bluetooth device and set it up as a key again.
I know you said you'd tried at least some of this, so my apologies if you've tried it all. AFAIK, the above procedure should completely wipe and re-provision all the relevant data on both the phone and the car as thoroughly as is possible short of a complete wipe of
everything (return to factory defaults), which would be a pain to restore. Of course, if the problem is a fundamental model incompatibility or, as
@5_+JqckQttqck suggests, an RF problem caused by a case, a software reset will do no good whatsoever.
If your phone is Android-based, some people (including me) who've tried both on identical hardware say that Android 9 ("Pie") is more reliable as a phone key than is Android 8.x ("Oreo") and earlier. Thus, if you're running Android 8.x and you can update to Android 9, doing so may help. If your phone's manufacturer hasn't released Android 9 for your phone but you're technically proficient, you could look into an open source Android like
LineageOS; however, LineageOS seems to be more susceptible to a
problem with making Bluetooth calls, so you might be trading one problem for another. If you're not technically proficient or don't want to bother with replacing your phone's OS, an upgrade to a newer phone may be worth considering.