in my mind, the first email would be encrypted using a public address obtained by asking for the key from the receiver's domain's server, or otherwise leveraging the DNS for the receiver's mailserver.