I remember plenty of issues with USB device compatibility. Mostly when someone failed to follow the standards, of course—fully compliant devices and host controllers have generally worked well together, at least since USB 1.1. But there are a lot of non-compliant devices out there. Bluetooth isn't much different in that regard: if both devices follow the spec it tends to work well, but it's much more likely that one or both of the devices takes a "shortcut" or two in the name of saving a few cents. The fact that Bluetooth devices are typically battery-powered and thus strongly incentivised to cut corners to save a few milliwatts doesn't help.
However, the standards certainly aren't perfect even when implemented correctly. The most awkward aspect of the Bluetooth experience, in my opinion, has to do with pairing. There shouldn't by any limit to the number of simultaneously paired devices. They should just exchange signed credentials during the pairing process, and either device (but typically the more general-purpose one, such as the phone or laptop) should be able to present these pairing credentials later to establish a connection. The headphones, car stereo, or other special-purpose, storage-limited device shouldn't need to remember anything about the devices permitted to connect.
I remember plenty of issues with USB device compatibility. Mostly when someone failed to follow the standards, of course—fully compliant devices and host controllers have generally worked well together, at least since USB 1.1. But there are a lot of non-compliant devices out there. Bluetooth isn't much different in that regard: if both devices follow the spec it tends to work well, but it's much more likely that one or both of the devices takes a "shortcut" or two in the name of saving a few cents. The fact that Bluetooth devices are typically battery-powered and thus strongly incentivised to cut corners to save a few milliwatts doesn't help.
However, the standards certainly aren't perfect even when implemented correctly. The most awkward aspect of the Bluetooth experience, in my opinion, has to do with pairing. There shouldn't by any limit to the number of simultaneously paired devices. They should just exchange signed credentials during the pairing process, and either device (but typically the more general-purpose one, such as the phone or laptop) should be able to present these pairing credentials later to establish a connection. The headphones, car stereo, or other special-purpose, storage-limited device shouldn't need to remember anything about the devices permitted to connect.