Connection/pairing problems with Fairbuds XL

Recently I am not able to connect/pair my Fairbuds XL to other devices reliable. Even my FP4 often does not see them if I try to add them. I often have to do several restarts of the headphones which was not the case when they were new.
Has anyone experienced similar problems and solved them or is there a way to factory reset the headphones?

I never had that issue with mine.
You could try a factory reset:

To reset all settings on the headphones, press and hold the joystick button to the right for 5 seconds until you hear the confirmation.