Bluetooth LE, which is used for wearables like smart watches etc, supports address randomization and it has mechanism for finding paired devices even though the address changes. Bluetooth LE devices must advertise for other devices to be able to connect. Many headsets nowadays use classic Bluetooth for audio streaming and handsfree but in addition they use Bluetooth LE for configuring the headset through their app. That is why the headsets are often advertising all the time.
As a side note, contact tracing apps are making our phones also to advertise. Fortunately they are using address randomization properly to ensure phones can't be tracked.
Were the headsets all in "discoverable" mode ? Are headsets announcing their MACs even when not in discoverable mode ? Or do they broadcast their MACs in plain text even during a paired&encrypted connection ?
I've experienced this reliance on MAC addresses by trying to use Bluetooth headphones in a dual boot system. Every time I switch operating systems, I need to repair. Same with phones that have been factory reset. Peripherals seem to assume that a device (MAC address) uuniquely identifies the other end of the connection (which it actually is supposed to, so fair enough). You can probably use random addresses for scanning for new devices, but for any active use of the protocol you're going to need to stick to a given address. As long as you only use one device at a time, that address can probably be randomised for each device, but that's a hard sell that strongly limits how Bluetooth can be used.