Concurrent recipient resolution and certificate acquisition. If a client-entered input data may be resolved without further client input, the server resolves the input data into a recipient entry that has an associated routing address. The server then transmits a response to the client that includes the associated full display name, routing address and certificate. If the server determines that the recipient entry cannot be resolved without further input from the client, the server identifies a number of possible recipient entries, and for each possible recipient generates a token, which is then communicated to the client. The server receives a subsequent request from the client identifying a selected one of the possible associated recipients using the associated token. The server then acquires a certificate associated with the selected recipient using the token, and then sends the certificate to the client.