Thats why there are no mehadrin food store in Ben Gurion airport.
But technically when your trying to certify kosher food where do you draw the line? If the waitress are dressed inappropriate is that a hashgacha issue? If the place is a hangout, has bad music, is that a reason to pull the hechsher? Unless the place is making chometz on pesach the food is technically kosher even if they are open on shabbos. So unless there are better options available some out of town Hashgachos feel its better to have kosher food available to the general public then to be machmir on other principles.
The shomer shabbos customers on the other hand should definitely be looking for shomer shabbos establishments with tznius waiterss etc to buy their food.
Actually there are a couple mehadrin restaurants at Ben gurion.
And to the question of where to draw the line with other halachik infractions- some reputable hechsherim may vary from others, but one thing is agreed upon by all: There is a line. No one would give a hecsher to food in a strip club no matter their clientele. I would guess that some of these phony hechsherim would.
In regards to a Jewish store staying open on shabbos, IINM both the food prepared on shabbos and the pots used to cook the food would be assur, whether or not the food was made by a Jew.