I think the key here is going to be coming up with robust protocols for user verification; you can't run an army of spambots if you can't create thousands of accounts.
Doing this well will probably be beyond the capacity of most instance maintainers, so you'd likely end up with a small number of companies that most instances agreed to accept verifications from. The fact that it would be a competitive market - and that a company that failed to do this well would be liable to have its verifications no longer accepted - would simultaneously incentivize them to both a) do a good job and b) offer a variety of verification methods, so that if, say, you wanted to remain anonymous even to them, one company might allow you to verify a new account off of a combination of other long-lived social media accounts rather than by asking for a driver's license or whatever.
And of course there's no reason you couldn't also have 2 or 3 different verifications on your account if you needed that many to have your posts accepted on most instances; yes, it's a little messy, but messy also means resilient.