I had a similar idea, and I suspect that address randomization isn't as big a problem as you might suspect, since many people have a paired device (i.e. headphones), and that pairing often uses classic Bluetooth, so it must have a fixed address. The burglar's car is also likely to broadcast unrandomized bluetooth if it's in the area, also.

But the real trouble with this system is that the police aren't going to do anything with this data unless there's a murder. Even if a bluetooth device were stolen and you could locate it, the police will not likely help you recover anything. And this assumes that they even understand what this pissed-off nerd is on about.

Amazon, however, could build a bluetooth sniffer or IMSI catcher into its devices and sell the resulting data to law enforcement, who could then avoid the time and expense of getting a warrant for location data. Assuming that the police care at all about property crime, this would achieve the goal.

As far as I know the way Bluetooth is implemented in many devices prevents it from working if you change the MAC address all the time.

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.

The Bluetooth classic, the variant which is typically used for audio and handsfree use cases, does not support address randomization. However, Bluetooth classic device does not necessarily need to be in discoverable mode for paired device to be able to connect. Typically they are discoverable only when they are set to some kind of pairing mode.

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.

Assuming that all these headsets are bluetooth "classic", since I am yet to see a bluetooth low energy headset, how could they be tracked, anyway?

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 ?

You could have use a stingray to capture their IMSI

It really annoys me that changing an IMEI is a crime in many countries. The mobile stack has tracing built in a low level, and is genuinely impossible to use anonymously.

Does it matter that you can't change the IMEI? Your IMSI identifies you anyway.

Both are used over the air during the initial attach. If you're trying to hide from (I assume predominantly) the authrities, then it's possible to see that you've switched SIM cards into the same handset.