James Joyner sides with Julian Sanchez against Radley Balko on the merits of government inspections of restaurants.
I’m pretty sure some libertarian—I want to say it was Charles Murray, in What It Means to Be a Libertarian—made an argument for optional regulation (not just for restaurants, but also in any regulated business): companies could choose to be regulated by the existing regulatory regime, or opt to not be regulated. In the latter case, the non-regulated companies would be required to display some “not regulated” symbol or disclaimer; of course, they could also opt for a private regulatory regime (like the ones Balko proposed hypothetically), and businesses would presumably show their “private stamp of approval” next to their “not regulated” symbol.
This is not unlike how university accreditation works in the U.S., although there is no legal requirement to put up a big “we’re not accredited” sign (at least, not that I’m aware of, although there are other meaningful disincentives—like denial of federal aid to students).