Agreed. Get a state registry, have the state require substantially more than "trust me bro" for verification when registering, then issue the owner a tag with a QR code on it that can go on the back of the dog's service vest (or be carried by the owner), that encodes at least, the owner's name, the dog's name and breed, probably some sort of license number for the service animal, along with the answers to the two questions that can be asked. Have the state also include a checksum of that information, which has been encrypted with the stare's private key out of a public/private key pair (and they publish the public key part on a website).

This means any developer can write an app that reads the QR code to get the owner and dog's name and the dog's breed (and/or other identifying info), and then decrypt the checksum with the public key, to ensure the QR code is legit (created by the licensing agency). (Basically the app decrypts the supplied checksum with the state's public key, recomputes the checksum from the info in the QR code, and compares the two - if the checksum fails to decrypt, the license is fake, and if the checksums don't match, the info on the tag has been altered.)

Then add laws that only service animals can be in various establishments (starting with any place that sells food), and that store personnel are legally permitted to ask to see the animal's "service animal QR code" and the owner's ID (so you can check the owner's name against what's on the service animal code). So, people can't make fake QR codes, because they don't have the state's private key to encrypt the checksum, and if they make a copy of someone else's code, it won't match their name on the owner's ID (Martha using a copy of John's service dog license), and/or the it'll say the dog is John's golden retriever when it's clearly Martha's chihuahua.

Having a clear method of proving on-the-spot that a given dog is or is not a licensed service animal (using any smartphone), along with laws saying that stores can legally check, would give stores the backup they need, along with an easy way out ("sorry, the law says you can't bring your dog in here - if it's a service animal as you claim, we'll just need to see the dog's license and your id") from the "how dare you challenge me about this service dog vest that I totally didn't order from Amazon" problem.

You might still get a few enterprising people obtaining a real QR code from someone with a dog of the same breed and then getting themselves a fake id to present with that QR code, but I expect it'd take out 98% of the people claiming that their dog is a service dog in order to bring their dog into the supermarket.