Thank you for your feedback.
Did some testing yesterday, and of course I did not experience the issue at first. Two hour long drives and no problem. Seems this only occurs for short trips, taking the kids to kindergarden or driving to the store. These trips only take 2-3 minutes (yes I am lazy), but it seems that the connection between phone and car have not been properly initiated before I turn off the ignition.
Then finally, I took a half an hour drive and made a phonecall while connected, and when I returned home, the phone had to be rebooted. I tried to update the BT drivers, disable/enable the rSAP service and even uninstall/reinstall BT drivers, but nothing worked.
This annoys me, but furtunately the reboot takes less than a minute with CyanogenMod
I have not tested with Samsung firmware, so I am unable to comment if issue was present there as well.