I agree with Nick that you have noted a big hard problem, with Zooko’s triangle type trade-offs. (For a semi-related example that is “easier” but still crazy difficult, see our “PeerFlow: Secure Load Balancing in Tor” https://doi.org/10.1515/popets-2017-0017 )
As noted or implied already in this thread: in the end, if someone can cheaply spin up indefinite unlinked identities and build good reputations for them, and if trust is based on such reputations, it is hard (impossible?) to avoid them spending as many of these identities as needed for whatever proscribed purpose they want.
I have been working with Nick on applying what I call contextual trust to AT protocol handles and DIDs (also connecting them to onion addresses). I’ll be talking about this at ATmosphereConf. One of the nice aspects of contextual trust is that it scales both up (unlike e.g. PGP web of trust) and down (unlike TLS CA infrastructure). This might help with your newcomer problem: newcomers can get a contextual sattestation (self-authenticating attestation) about their identity from an entity offering just generic, anyone, structural-level guarantees (think Bluesky verified identities perhaps, though if they don’t have the needed requirements for that particular endorsement, somebody might set up an endorser offering something lesser than that). This would be for general system-wide trust. They might lack any built in cross-domain identities (or do not want to link to those), but they could still be validated within some existing context (member of some group, perhaps employee of some company that has an AT identity, or people Nick knows from swing dancing 
or …) If they are completely starting from scratch about their identity, then yes I think all they can do is build connections “the old-fashioned way”.