I have been having the same issue, also with a Pixel 9a.
It had been previously connected to my work truck stereo (Isuzu 4.5 years old) with no issues. Then when my regular truck was in for service, I had to drive another one for a few days, Same model Isuzu except about one year newer. When trying to connect to the newer truck, the connection sat there thinking about it for a little bit, then came up with 'connection failed' on the stereo, and a message on the phone saying 'Can't communicate with MAC ADDRESS'.
I thought it was an issue with the name of the stereo being the same as the one from the original truck causing a conflict in the phone (they both just say ISUZU), so stupidly, I deleted the original one for the regular truck, and tried again. It still failed. I gave up thinking it was only a few days, and I could live without it.
Then a few days later when I got the original truck back, I went to connect it again, and it fails the same way as the other truck. So now I can't use the bluetooth connection in a truck that has never had an issue previously with GrapheneOS. I have been driving this truck since it was brand new, and using GrapheneOS the whole time. I started with a 3a, then a 4a, then 6a, and now 9a. The annoying part is it had been working just fine with the 9a just a few days earlier, with the original connection I made when I got the 9a about 6 months ago. But now that it needs to be connected again from scratch, it won't do it.
I have tried every other phone I can get my hands on in this truck, and nothing has any issue connecting to it at all. I have tried 3 iPhones, and 5 other Androids, all of them connect virtually instantly when I enter the 4 digit code. Only my GrapheneOS 9a fails. I have not tried one of my older phones, but that will be my next test. I will take the old 6a to work, delete everything from the bluetooth list, then try that. It has been sitting in a drawer for the last 6 months, and has not been updated since.
I can only assume something got broken in one of the updates sometime after I did the initial connection to the truck stereo.
I have tried reseting the bluetooth in the phone's reset options, and it didn't fix it. Luckily it still connected to my car stereo, as I was worried it may not do that too. I have tried most of the suggestions in this thread, but nothing has worked.
I have since updated the phone a couple of times, it is now on build 2026040800.
When is this likely to be fixed, as it's most certainly an issue with GrapheneOS (not a single other device has an issue connecting to the same vehicle stereo). I'm in my work truck 10-12 hours a day, and it would be really nice to be able to answer my phone when it rings without breaking the law.
What good it the most secure OS available when it can't even do basic bluetooth connections like every other device on the planet?