For a new businessman or professional setting out in the world, pre-Internet, "establishing your name" was a requirement. These days the concept's often referred to as "creating a personal brand", but the reality was pretty straightforward: how does an unknown quantity become a known quantity?
A common method was the professional or social introduction. This is still practiced, where a third-party _matchmaker_ will introduce two parties. The matchmaker usually knows both, and can vouch for the newcomer and smooth the path for introductions with the established party. Essentially, the matchmaker stakes _their_ reputation by speaking for another.
Lawrence Lessig describes a similar concept in his book Code and Other Laws of Cypberspace, in a passage describing a physical messaging system, the Yale Wall. This was a board onto which messages could be posted, with the proviso that that they be signed. Unsigned messages would be posted from time to time, effectively presenting an anonymous viewpoint. Removal wasn't instantaneous or automatic, but rather, at some point prior to garbage collection, another individual could review the piece, and, if they felt it warranted posting, sign for it. They weren't registering themselves as author, but as vouching for the merits of the viewpoint -- not necessarily agreement.
A messaging system in which a new peer might be able to indicate that, hey, peers X, Y, and Z, with established reputations can vouch for me, and for which those peers could confirm their endorsement, might address the "how to build reputation" issues of new mailservers.
I've also found that even large mail systems will frequently have some procedure for getting at least provisionally vetted, effectively a workfactor cost to coming online. Though the process absolutely could be improved.