I bought a bluetooth speaker for my car and when I turn it on, it's not on pairing mode, it will search for any device that paired with, so even if I have my iPhone's bluetooth on, they will not connect if I have not set up the pair mode for the first time. I have to put it in pairing mode and then I go to my iPhone bluetooth and once it finds my bluetooth speaker I select it and enter the code.
After I finished pairing it, the next time I turn on my bluetooth speaker it will search for any device I've paired with it without going on pairing mode and then it gets connected with the iPhone automatically. I only need to do the pairing mode once and only the first time.
If you're saying you're headset does not have a separate pairing mode, please double check your headset's manual, if there is really no pairing mode then I'm sorry but I can't help you. I don't know what else you can do.