Your analysis is interesting, but so far fetched I'm not going to worry about it. I mean, yes, if the 5 billion people of earth decide to do this, or decide to call each other, or decide to send each other snail mail, everything will collapse. Considering this as a worst case, in my opinion, is a waste for right now, and will deter useful work before it even starts. Agreed. I guess what I was trying to say (though I didn't actually come out and say it) is that the load is O(N^2). While not a problem now, it would be nice to find an O(N) solution. Or, more likely, an O(Nlog(N)).
Plus, it is ONLY necessary to retreive all messages if you don't want it know who you are communicating with. If you don't care if it is known you communicate with some psuedonym, then you don't have to get all the messages. The primary goal is to not mail messages out since that is where most the complaints against anonymous remailers lie. Indeed. If we go with a restricted message haven, the problem becomes very simple. Maybe we should attempt to get this working first.