The simple solution is to simply require any service animal to be registered and tagged with a government issued tag that would be difficult to counterfeit... But unfortunately all the disabled people would be up in arms at the thought of having to do anything that might inconvenience them, even though the result will eventually be outright bans of all service animals which I suspect a business could reasonably enact on the grounds that some people are allergic to dogs and that service dogs put those people at risk of death.  

Frankly, we should probably just ban them all outright except for seeing eye dogs.  Pretty damned simple to tell if someone is blind, everything else is just BS.