A Trust Email Datastore (TED) system is employed to maintain a list of message addresses with associated trust ratings. The trust rating of a message address is derived from an underlying message address relationship network around the message address of interest through various network related activities such as message sending, forwarding, deleting, blocking, marking as is/is not spam, saving to address book, etc. There may be at least two components of the trust rating between two message addresses. One component of the trust rating, called a relationship trust, may be determined based on proximity of two message addresses in a message address relationship graph. Another component of the trust rating is substantially independent of the positions of two message addresses in the message address relationship graph, and is referred to as a universal trust rating. The trust rating components can be combined and employed for spam filtering.