But these cases are the norm, rather than the exception.

Well, you're lucky, you live in Berlin. Most of the payments I make with Bitcoin are online, to websites. So this will differ between people.

I wonder how critical it is. Let's say you are paying for a meal. In your head the place you're at is just "the little Indian restaurant on the corner". In the companies register and therefore certificate it's something like "Singh Food GmbH". That's probably good enough to prevent shenanigans. Even if there's a virus on your phone, it can't really replace the cert with a random stolen one, otherwise your meal could show up like "IronCore Steel Inc" or something that's obviously bogus. It'd have to be an incredibly smart virus that knew how to substitute one name for a different one, from a large library of stolen identities, such that the swap seemed plausible. That sounds very hard, certainly too hard to bother with for stealing restaurant fees.

And if a waiter at the restaurant is corrupt and they replace the cert with one that's for their own 1-man business "BP-Gupta" or something, OK, you might pay the wrong person by mistake. But eventually the corrupt waiter will be discovered and then someone will have proof of what they did. It's FAR more likely they'd just strip the signature entirely and try to convince you the restaurant doesn't use BIP70 at all.

Still, if we want to fix this, one approach I was thinking about is to have a super-cheesy CA just for us that issues certs with addresses in them, for any name you ask for. That is, if you say you want a cert for "Shamrock Irish Pub, Wollishofen, Zurich, CH" then it either sends a postcard to that address with a code to check ownership of the address, or it checks ownership of the place on Google Maps (which does the same postcard trick but for free!).

That doesn't work for vending machines, but perhaps we just don't care about those. If a MITM steals your lunch money, boo hoo.