Procedure was not as simple as it used to be with my Asus P525.
First I had to pair my headset (HT820) with the phone E63.
After pairing, headset must be set to discoverable again to pair with the a125s. Once the a125s and HT820 are paired, turn on the E63’s Bluetooth and it should automatically connect1 with the headset.
1 I’m assuming that the headset is an “authorized device”.