I am able to pair my (1st generation) iPhone with my 2007 Prius, and it works fine. If I turn the car off, then turn it back on while sitting there, I get the Bluetooth Connected Successfully message at startup. However, if I walk away, and then come back, the pairing is lost, requiring complete re-pairing to get a connection again. I've tried deleting the iPhone on the Prius and re-registering, tried deleting the HandsFree on the iPhone and re-pairing, but each time, when I come back, it is not recognized and I have to re-pair it from the start. Any help much appreciated!
While I can't promise this will work, it is a good place to start! First, delete the pairing on both the Prius and the iPhone, and then reset the iPhone by holding the sleep/home buttons until the Apple logo appears (ignore the screen which asks you to switch the iPhone off). Once the iPhone is back up and running, and before you open any other application, go to the car, and re-pair the handsfree and phone so that you get the 'connected' message. test the pairing by making a handsfree call. After that, power off the car, walk away, then come back and see if the connection is automatically restored as it should be. The one time I had this same issue, I found that worked - the critical bit being resetting the iPhone as described above, since over time it seems to get less and less consistent in behavior. If that doesn't work, delete the pairings again on both ends, and then connect your iPhone to your Mac or PC and perform a restore via iTunes, after which try pairing again.
Also, though it doesn't solve the exact problem you refer to (mine doesn't have that issue), you may want to consider using the "transfer call" button when walking away from a paired Prius (or when you're about to turn the car off).
While I never encountered your specific case, I agree that bluetooth connection is inconsistent at times. You don't need to completely repair the device - just set your iphone into airplane mode and back, and it should pair again.
