The car is a Subaru WRX 2012 with the base radio.
It did reconnect automatically for the last two years until I changed phones, deleted the old phone profile, then paired the new phone. It does work correctly when phone is selected, but when I restart the car I have to manually select the phone's profile in the car's bluetooth menu. In the past the phone would always connect and music would play within a few seconds of restarting the car, and I didn't have to do anything manually.
I have tried other phones to troubleshoot and still have same problem: the phone will pair, and everything will work, but after restarting the car it won't switch to the phone automatically and I have to manually select the phone in the car menu.
I want the old behavior back where the car "sees" the phone and switches to it right away when I start the car, continuing a phone call in-car or play music over the speakers seamlessly.