A trust network database has any number of nodes, each node representing a user e-mail address. Links between nodes represent whether one user trusts another. Trust (that the recipient is trusted) is established when a sender sends an e-mail message to a recipient. The recipient is effectively placed on the white list for the sender. A legitimate e-mail address creates a strong trust link, otherwise it is weak. A spam count tracks by an amount of spam sent by each node. Outgoing e-mail messages are screened to make a determination that the sender trusts the recipient and that information is added to a local or remote trust network. Incoming e-mail messages are first screened to determine that the sender is legitimate. Then, the sender and recipient e-mail addresses are forwarded to the trust network to make a determination as to whether the recipient trusts the sender. A score (based upon number and type of links into or out of a node, the spam count for the node, etc.) for the sender is returned indicating whether or not the e-mail message is likely to be spam. An anti-spam engine is bypassed, used normally, or used aggressively based upon the score.