1. A method for estimating a probability of spamminess for email messages, comprising: using a processor device, performing steps of: reviewing a sequence of IP addresses used in transmission of an email message, beginning with a last IP address and proceeding backward to an originating IP address, with intermediate IP address in between; comparing a current IP address in the sequence of IP addresses with an IP address in a training set; when the current IP address does not match any IP address in the training set, combining statistics of nearby IP addresses by: building a tree of known IP addresses, wherein a root of said tree has up to 256 first level sub trees, each first level sub tree corresponding to various possible first bytes of an IP address; wherein each node n in the tree represents an IP address; and at each node n in the tree: storing a count Sn of spam messages in which the IP address the node n represents has appeared; storing a count NSn of non-spam messages in which the IP address the node n represents has appeared; and computing a ratio that is a measure of spaminess s of the node n; wherein the ratio of the measure of spaminess s of the node n is computed by dividing the total number of messages that have come through the address, which is Sn/(Sn+NSn); determining an overall score for the message based on the ratio of spaminess of each node along the message path; wherein the overall score is calculated by calculating a weighted average of the spaminess s of the nodes, with the weight equal to 1/(s*(1−s); and determining a probability that the message is spam based on the overall score being greater than a defined spam threshold.