Vendors would display the label of whatever regulatory agency had certified them, and the agency would be less susceptible to manipulation or bribery, because they'd be selling their image.

I might be a statist, but I agree with that. When it works as intended, competition between producers/vendors of anything is a great social good for individuals, as it raises them to a position of power (see Mises et al).
However, I wonder if such agencies can't be made semi-public, or if they couldn't work like an advanced and well-directed banking system; there's a central government agency, which licenses and watches over municipal and private ones; its direct regulatory services would be very conservative, to create a stable "fallback point" for customers.