Any suggestions?
FWIW both of my BT-enabled ThinkPads have hardware and software switches to turn off BT in order to extend battery life. That suggests to me that BT hardware drains batteries fast.
My Moto KRZR requires that I explicitly set BT to scan for devices whenever I want to use them. Have you tried to pair the Nokia with a BT device an hour or more after you last disconnected to see if it pairs automatically. That would indicate that BT never got shut off.