Well, the keyservers also don't validate if it's your key instead of a key submitted by me with your email address on it, so for any secure messaging you need some other, authenticated channel for the potential recipient to assert which is their key.

Oh, that's a good point. Heh, I have one of those, too, which even caused a problem once[0]. I wouldn't expect people to find it first, though, because I wouldn't expect people to go to a keyserver first; I'd expect them to find my key on one of the places I have it listed on the web. I've never tried blindly entering someone's email address into a keyserver and just hoping they have a key; I've only sent PGP-encrypted email to people who list their keys on the web.

[0]How it caused a problem: I added an email address to my public key (or maybe it expired or something, I forget), and asked people to refresh their copy of my key. One person instead downloaded it entirely anew from a keyserver and got the old one. Oops. (Admittedly I didn't explicitly use the word "refresh".) Anyway yeah -- though this problem had happened to me, it hadn't ocurred to me that it might be common; maybe this is more of a problem than I thought...

>never-expiring keys

While this is bad, the keyserver issue is still valid.