Yes, apparently I didn't think this through. That leaves the nameserver combo method.
> Given the decentralized nature of DNS it's very simple to set things up before you change the nameservers, and this is widely considered to be the best practice. This also solves the "two accounts trying to claim a domain at the same time".
That only solves the someone trying to snatch your domain after they find out your nameservers have changed. They can still initiate the claim before you do for any other reason.
> I'm just not sold on the idea that it's their responsibility to solve this.
That's an opinion (flawed if you ask me), and has nothing to do with whether proof of ownership is technically possible. And if the pool of combos is large enough and uniquely assigned to each account it's certainly a technical solution to the problem.