Decentralized anonymity systems tend to be unreliable, because users must choose paths through the network without knowing the entire state of the network. Reputation systems can improve reliability by predicting the state of the network. In this paper we focus on anonymous remailers and anonymous publishing, explain why the systems can benefit from reputation, and describe our experiences designing reputation systems for them while still ensuring anonymity. We find that in each example we first must redesign the underlying anonymity system to support verifiable transactions.