I think most people in this situation do the same thing people do on Twitter when it suspends an account for nonsense reasons like telling a Nazi to eat paste: make another, make a post, share it with a few friends off Twitter/Mastodon, have them RT/boost to circulate it within their circles. This seems to work pretty well.

Cryptographic certainty is fun to think about, but sometimes you just need people.

It doesn't involve cryptography, but mastodon has for at least a couple of years supported link-verification in profiles (it basically checks if a link back to your mastodon profile exists on a page linked on your profile), so a linking to a page that only you credibly control (say, a personal website) is the de-facto system of decentralized user-verification on mastodon.

Edit: supported since 2018 https://github.com/mastodon/mastodon/pull/8703

It does sort of involve crypto: if the page you control weren't served over HTTPS it wouldn't be too hard (DNS poisoning) for someone else to trick a server into verifying the wrong user.

If DNS poisoning is so easy why don't you perform the same attach on Let's Encrypt since that also uses plain HTTP.

Certificate Authorities are extremely careful about DNS (and BGP hijacking), more so than basically everyone else.