Open Stack

> 
> Except for encryption you have to do those lookups on the sender side
> too, so you are back to square zero.

Overall, the encryption situation is not too different in the PKI vs shared-key case.

We shouldn't disregard improvements in signing performance just because they don't apply when encryption is used.  Most I've spoken to consider encryption a nice-to-have than a need-to-have. Signing seems to be the common case.
 
> Also doing lookup on the receiver you forgo the possibility of doing
> access control even before allowing to send any message, requiring
> access control on the receiving end (potentially a second lookup for the
> policy).

Potentially as part of the keying, but yes, this is a challenge. 
> Also doing lookups on the receiver end you open up to an attack where a
> malicious users sends thousands of messages *seemingly* coming from
> different sources causing the receiver to try thousands of requests
> against the server to verify a public key that does not exist.
> 

You can DoS a message consumer, period. Hell, if you get this far, you can probably DoS the keyservers without too much difficulty. With your suggestion, we'll need a specialized application running on each keyserver. That will limit how much you'll reasonably scale the keyservers introducing a greater chance of a DoS.  Overall, DoS of a message receiver by making it query the keyserver too frequently is probably not a concern at all, all things considered.

Regards,
Eric Windisch