We have a user who's Blackberry Storm requires him to enter his password everytime he gets into his car, is this a policy that came from the BES server? I have tried it with a defaulted 8830 and I get the same response.
You need to make sure that the connection setting for your car bluetooth are set to this.
Options>Bluetooth>Device Properties>Trusted>Yes
This will stop this happening.
The "Allow outgoing calls while locked" setting in the security menu just updates the locked menu to let you make calls without having to unlock the phone, there is an option in the bluetooth options menu "allow outgoing calls" which should be set to always though.