Since there are a couple of capacitors on the circuit's power rail there's always a bit of residue charge when the battery is disconnected. I noticed that this can be used to alleviate the voltage dip. So the simplest solution to the problem without adding anything extra is: power up, power down, then immediately power up again. And the bluetooth starts without hiccups.

Slightly ugly, but good enough for now.