Hi,
removing the cert data is one thing, but to make sure the old certficate
cannot be used again, it must be effectively revoked.
The (current) documentation states that puppet cert clean does in fact
revoke the certificate, so you should not be seeing this issue.
Which version of puppet is this?
Regards,
Felix