Just to reiterate: the problem is not that the phone and the car receiver won't pair. The problem is that the pairing won't stick.
What you are describing is a reset of the pairing, which will work as long as you don't shut off the power. But once you do, the audio pairing will be lost. The phone and receiver won't connect either manually or automatically after that.
I've tested this repeatedly on my Pioneer FH-P8000BT, and the results are consistent, both with my old iPhone 3G and new iPhone 4. As I've said before, this worked fine before, and the only variable is iOS 4, so the fix must come from Apple—everyone, please file feedback at:
http://www.apple.com/feedback/