Lo de la web de Correos no es un buscador, sólo sirve para ver si el certificado ha sido entregado. Y sólo si ha sido entregado mediante el sistema informático (SERADE)
La forma más rápida de ver dónde está un certificado es consultándolo en ese sistema desde cualquier oficina, aunque a veces los certificados no se graban en el sistema informático y entonces no aparecen. Eso no quiere decir que estén desaparecidos, simplemente que figuran en "hojas de control" hechas a mano.