In the UK the phone book is downloaded after pairing, its optional.
From that I take it that the phone book is stored in the head unit.
It is slow to connect and ready the phone on starting the car, but I take that to be the slow electronics in the head unit, probably a processor?
Only problem I have with my HTC wildfire is playing via BT, for some reason the music starts to play then immediately cuts off, so I have to bring the screen up and press play, they may be a better way but I haven't found one yet.
I get the impression that a car doesn't exist that has a problem free head unit, my last car the phone book would only download manually, one at a time!