[bracewel]

Either wait for the certificate to expire, register a new certificate for the domain with another CA which LE will see and can then be used to prove ownership, or ask the originally issuing CA to revoke the certificate which will remove the need for the challenge completely.

[devit]

I interpreted "you must prove control over both the server and the key used in the existing certificate" as meaning that if a Let's Encrypt certificate for the domain has been created in the past, you need to own its key (presumably proved by signing something with it) to get another one.

Is that wrong?

Waiting for certificates to expire could mean waiting for years, unless they have auto-renewing very short-lived certificates (but then you have the same problem for the authentication used to automatically get those certificates).

[MatthewWilkes]

LetsEncrypt does use very short-lived certificates (90 days) for this reason. However, you have to remember than when you buy a domain you already have no idea if any CA has issued valid certificates for it.