For some reason when the Arduino is started and the servo resets to its default position the HC-06 fails to start up properly. If the servo is connected after the start-up everything works fine. I guess there's some kind of an interference or drop in power due to the servo and the HC-06 starting up at the same time, even when neither of them are powered from the Arduino. A capacitor between VCC and GND doesn't seem to help.

Switching the servo power on separately with a switch or a transistor should fix the issue if nothing else works.