It definitely depends on the individual make and model car, not just the S3. I've been trying to get BT working with my 2012 Honda CR-V for months and my experience was always the same:
1) Initial pairing OK -- both car audio and media
2) Turn off BT on phone
3) Second pairing a nightmare -- even with saved profile
4) Remove all BT profiles from the car, start over -- with step 1)
Found that if I left BT running on the phone ALL the time, that in some cases, the phone WOULD pair with the car, but in ALL cases, car audio did NOT pair. I had to go into settings and check that EVERY SINGLE TIME.
Then, I bough an iBolt Card Dock (from local Verizon store) and installed Car Home Ultra on the phone.
NOW, phone and car pair perfectly -- including car audio -- every single time!
Don't know if it was just the car dock, or the addition of Car Home Ultra, but pairing now works without any problems.