It would only have to go onto the CRL until it expired. The CRL would become large, but it would still be a couple of orders of magnitude smaller than the global DNS itself, and we manage to deal with that OK.

The idea would be that the certificate comes with the domain name, as the whole ball of wax. Verisign aren't the only _registrar_ though - GoDaddy, MelbourneIT etc. are all registrars - VeriSign's claim to fame is that they manage the .com _registry_.