Someone could make a program that inspects the packets on your local network. If they're encrypted then the connection is safe. They could then start a register of VPNs and rate them.
This is just the start though, you'd also have to guard against common keys and other various gotchas.
Also, another idea is VPN providers might start seeing it as a business opportunity to provide robust, secure connections and advertise how they work. These claims could easily be verified.
Just a start, I'm not an expert in networking, but it seems fairly doable. Obviously MITM is always possible if you're not connecting via ssl.
Also, this could be the impetus for further decentralizing the internet, although who knows how far that's out. The centralization of the internet might have taken things too far and killed the golden goose by abusing their position, incentivizing an acceleration of full decentralization, like with IPFS and their ilk.