I have tried my daughters SIII, which is with a different service provider. Exactly the same; the car sees the phone and pairing seems to take place OK. Then;
1) The handset shows the VW Premium as paired.
2) The handset appears in the cars listing.
3) When the ignition is switched on, and only the SIII is present, the car searches through its list of handsets and does not link to the SIII. The massage appears in the car, "No suitable handset detected" or something to that effect.
My Nokia's are working fine, as they always have done !
What a shame, the SIII is a great handset.