The tattoos here in B.C. are a combination of letters and numbers. Each year the BCVMA chooses a letter that will be used and the other letter is one that is specific for each clinic. The numbers are chosen numerically so on January first, the first tattoo at a clinic might be JF001 (the letter J would be a clinic if that was their letter and the letter F would be the 2008 letter provided by the BCVMA, not sure what letter they are going with, just using that as an example and the number 001 would reflect the first patient being tattooed at that clinic in 2008. The books the BCVMA distributes to all the clinics each new year has all the clinics letter combinations so tattoo letters can be easily looked up to locate the hospital. There is also a section with the letters of clinics in nearby provinces, or at least there used to be.
If a person moves and changes their phone number, they just need to provide the new phone number to the hospital or shelter that did the tattoo so they can update the records.
I agree, tattooing a phone number on a pet would be a big commitment and because phone numbers so often change, probably not a good idea.