This in my opinion is a problem with all Windows Mobile devices...at least for me it is. The only real way to fix it in my experience is to either flash to a more updated ROM that may have updated bluetooth drivers, or to keep doing what you are doing now and soft-reseting until it works right. Its a problem with the drives not being loaded into RAM if I remeber correctly.
Verizon Motorola RAZR LTE
Acer Iconia A500
Custom Stock 4.0
Acer STOCK 3.0->Custom Stock 4.0
HTC S620 Excailbur->HTC Wizard->HTC Juno->HTC Herald->HTC Tytn II->HTC HD2/HTC Shift 9500->HTC G2/SGT ATT->LG G2X/SGT ATT->HTC Sensation/SGT ATT->Motorola RAZR LTE/Acer Iconia A500
PARADIGM SHIFT!! Now on Verizon USA.