A system and method for searching and retrieving certificates, which may be used in the processing of encoded messages. In one broad aspect, a message management server generates certificate identification data from a message that uniquely identifies a certificate associated with the message. The certificate identification data can then be used to determine whether a given located certificate retrieved from one or more certificate servers in response to a certificate search request is the certificate associated with the message. Only the certificate identification data is needed to facilitate the determination at a user's computing device (e.g. a mobile device), alleviating the need for the user to download the entire message to the computing device in order to make the determination.