Could you build a certificate revocation system on a blockchain? At least it should be obvious if someone is MITMing you (you don't get new blocks for ages), and other than that, you have a permanent record of all revoked certificates. The people who keep the chain running also get compensated.

Doesn't necessarily help mobile, due to the blockchain's size... but perhaps there's workarounds for that.