Unable to pair again bluetooth headset
OK, I got this idea: maybe it's the headset that is preventing the pairing from happening (remember I removed the pairing on the Mac, but on the headset it might still be somehow locked with the previous pairing for this specific device). When I read the manual a while ago I remember there was a way to clear the pairing settings.

So I did that, and voilá!, I can now pair with the Mac again :-)