It has to be initialized in heading hold or as you said, it will never go into heading hold.

Whats happening is that the gyro is booting faster than the receiver

Binding sets fail safes. During boot up, before the reciever and transmitter connect the reciever sends fail safe position to the servos (and gyro gain wire). So if you set that failsafe to heading hold, thats what it will get during boot up.

If it comes up in rate mode and you disconnect and reconnect the battery, the reciever goes into quick connect and gets the proper signal before the gyro initializes and it looks like that fixed it.