A system and method for searching and retrieving certificates, which may be used in the processing of encoded messages. In one embodiment, a certificate synchronization application is programmed to perform certificate searches by querying one or more certificate servers for all of the certificates on those certificate servers. If all of the certificates on a certificate server cannot be successfully retrieved using a single search query, due to a search quota on the certificate server being exceeded for example, the search is re-performed through multiple queries, each corresponding to a narrower subsearch. The invention enables large amounts of certificates to be automatically searched for and retrieved from certificate servers, thereby minimizing the need for users to manually search for individual certificates.