you should call an attorney even if you get the keys back. just because they may not have left the keys in it, does not necessarily mean they their actions were not negligent. like others have said, if there is no fence, no lights, or if they just left the doors unlocked as a common practice, that might be enough.
only catch is that it will be difficult to prove if they left the doors unlocked. you know they'll deny it.
a lot of your case has to do w/ where this place is (high crime, etc....), whether it was night or day when stolen and if the owners had prior thefts on their lot or in the area.
the shop (or their ins. co.) will argue that the criminal acts of 3rd parties (the theives) obsolve them from liability. this however is not the case if the car was stolen in part due to their own negligence.... if they knew (or should have known) that is likely that a car would be stolen from the lot & they should have taken security measures to avoid thefts (i.e. fences, lights & locks).
and yes...definately don't pay them for the work (at least not yet) until a resolution is reached.