This is the solution, yes. I don’t have any headphone recommendations since I haven’t looked into this myself, although I do know that the randomization is part of Bluetooth Low Energy, so any headphones that don’t use BLE can immediately be ruled out. However, I don’t think LE Privacy is mandatory in BLE, so I also don’t think you assume anything with BLE does randomization unfortunately.
It might not be the perfect solution anyways though, I know I’ve seen a number of articles like this one, and I don’t know where this research ultimately ended up:
Thank you for your replies! I did a bit more digging and it sounds like the BLE part of this is, indeed, crucial.
It sounds like Bluetooth versions that support LE also support Bluetooth Classic (which definitely does not randomise MACs). Further, it sounds like LE has only recently become available for audio purposes, and devices don’t yet widely support the relevant LE audio codecs.
So I think it might simply be a shortcoming of Bluetooth audio for most products at present!
Disclaimer: I am fairly new to this, so may be incorrect. Please do correct me if so!