Creo que hay un par de ideas erróneas.
En primer lugar, los navegadores solicitan y verifican el certificado sobre la marcha. Ellos no lo almacenan. Esto se puede hacer manualmente, pero no es común ni útil en casos estándar.
Si alguien ha logrado obtener su certificado y la clave privada correspondiente, ahora "posee" un certificado perfectamente válido para su sitio y puede usarlo cuando lo desee. No importa que haya usado el certificado solo para pruebas y planee comprar uno nuevo. Los navegadores no son conscientes de esto. Aceptarán cualquiera de los dos certificados, bueno, a menos que su CA revoque explícitamente el anterior.
Así que simplemente comprar un nuevo certificado no resuelve el problema. No cambia el hecho de que hay un certificado potencialmente comprometido que podría usarse para un ataque de hombre en el medio contra el sitio.
Es ciertamente molesto pagar dinero extra por la revocación, pero en realidad no hay otra opción. Sin embargo, debes elegir un CA más justo la próxima vez. ;-)