Managed to do a factory reset of the headset, but the controller still won't pair. The controller that came with our second headset does pair on both headsets, so I think it's an issue with that specific controller.
I did recall seeing that it was trying to update the controller before the issues appeared with that controller. Maybe the firmware of the controller got corrupted.
Is there a way to factory reset the controller?