A system and method for searching and retrieving certificates, which may be used in the processing of encoded messages. In one broad aspect, a method is provided in which a certificate search request is received, a search of one or more certificate servers for certificates satisfying the request is performed, located certificates are retrieved and processed at a first computing device to determine data that uniquely identifies each located certificate, and search result data comprising the determined data is communicated to a second device (e.g. a mobile device) for use in determining whether each located certificate is already stored on the second device.