The more I think about this topic, the more I think the first task at hand
is to implement secure, private messaging...the nature of any messages
(payment requests or otherwise) sent between wallets is such that it needs
to be secured.  And the great thing is that it's easy to do and you don't
need to solve the PKI problem.  Have the wallet maintain one or more ECC
key pairs for the purposes of signing and encrypting messages.  Allow these
to be shared between wallets, or exported/imported, etc.  You can punt on
the whole topic of verifying the others' public keys using PKI (I mean,
people use bitcoin addresses today without the use of any formal or
explicit PKI to verify them...people will make do without it for
communications keys just fine...and they can always use PGP or other PKI if
they feel the need...most people would just pick up the phone to verify a
friend's public key)...this also doesn't preclude the use of X.509 for the
merchant/customer scenario...

For a payment protocol, you could do something like this: use https & ssl
certificates/CAs as one method of obtaining an ECC public key...pki_type
could be "https" and pki_bytes could be a url for the https location to
download the ECC public key.  The software would reject (or warn) if the
SSL certificate isn't considered valid by the normal CA validation process.
 The wallet would not necessarily need to permanently store ECC public keys
obtained in this manner.  This approach doesn't require people to obtain
new certificates just for bitcoin.

In fact, there would be very little difference to the proposed payments
protocol if this approach were taken...instead of using X.509 directly for
signing and encrypting messages, you are using it for signing and
encrypting the ECC public key exchange.  And this allows people that don't
have web servers or SSL certificates to exchange their ECC public keys by
other means and be able to use this payment protocol as well as any others
that one could imagine.  So, I actually think this is a better way of
keeping PKI out of the scope of the proposal.

Payment requests are just one kind of messaging between wallets.  I've also
mentioned the "cheques" feature.  I'm sure there are many more
possibilities.  Having a uniform method of securing messages sent between
wallets (that doesn't depend on external tools) would be a great step
forward IMO.