An anti-UCE system comprises a certificate issuance module configured to issue certificates to e-mail users and to maintain a registry of issued certificates with an indication of validity for each issued certificate. There is a plurality of possible certificates, each having a class with associated terms of service defining e-mail transmission limitations for the class. A certificate status module determines whether e-mail signed using the certificate violates the terms of service for the class. A filter module receives e-mails intended for e-mail users, and is configured to determine if a received e-mail is signed with a certificate from the plurality of certificates and, if signed, to determine from the certificate status module if the certificate is valid based on an identity of the sender and a class indicated in the certificate, and to forward the e-mail to an intended e-mail user if the certificate is valid.