A method, system, and computer usable program product for verifying and enforcing certificate use are provided in the illustrative embodiments. A certificate is received from a sender. The certificate is validated before communicating a message associated with the certificate to a receiver. If the certificate is invalid, a policy is selected based on a type of invalidity of the certificate. An action is taken to enforce the policy for using the certificate. The certificate may be received from the sender at a proxy. The validating may further include verifying the validity of the certificate using a certificate from a certificate database accessible to the proxy over a network. the proxy may copy a part of the certificate database to a second certificate database local to the proxy. The validating may further include verifying the validity of the certificate using a certificate revocation list accessible to the proxy over a network.