Later, the salmon is served and has bread crumbs all over the surface. You point this out to the server and they say "Oh, sorry, it does have bread crumbs."
Is the server or chef incompetent because they didn't answer the question correctly? Maybe not. Maybe they just don't have the appropriate experience to answer that question. Are they lying? Probably not. It took me three years to get wheat out of my diet. Why would I expect someone who is new to the idea to be able to sort out what has wheat and what doesn't have it expertly?
Why is it any different with a chef who cooks Paleo, but has no experience cooking Paleo. They might add a sauce or some other ingredient that has a grain or high fructose corn syrup, and maybe they just missed that on the label. I'm hiring the person because they know how to cook. I'm not hiring them for their ability to understand and articulate Paleo concepts.
There is nothing wrong with testing to make sure you get what you are paying for? No, I don't see it as insane.