I don't get much work done at an LBS as I can usually do it myself but this year I happened to have a couple of jobs which were beyond me. After they did a good job on the first one I got them to do the second one too. Both times I was given a numbered receipt the other half of which was attached to the bike or part so there could be no mistake. I just assumed that this was standard practice.
I would be surprised to find that any two bikes are identical once they've been owned for a while, even of the same year or model since riders like to fit their own choice of pedals, saddle or grips, and other accessories such as bells.
If someone else claims your bike the bike shop can surely trace them via till receipts, transaction records or local knowledge. It would get expensive replacing customers' bikes otherwise, they must protect themselves somehow.