Banks over here only reset those tokens with instructions sent to your known address. You can only change that address with a working token or showing government issued ID (which everyone around here has and is also required to open an account in the first place). At worst you need to send a copy by mail but going to a branch or post office or a video chat are more common.

Banks can always ask you to go into a branch for more important things like that. They do that in the UK. If you're not in the country, you can write a letter on paper and have the local police or lawyer confirm your identity. I've done that before. It's a nightmare but it eventually works.

In such cases the bank would offer to send new tokens by physical mail to the registered address or receive them in a branch with proper ID.

I recall a case where an important customer was stuck abroad with everything stolen; they were sent replacement tokens and cards to be received at the embassy, which could properly ID them.

Why can a bank have such a robust procedure for replacing tokens, and be trusted to follow it, but not have a similarly robust procedure for handling password resets?

They definitely can, but some of them don't, especially in USA for various reasons.

I mean, any bank with proper procedures doesn't really have the concept of "online password" that's sufficient to do anything and makes 2FA mandatory; I believe in EU now it would be forbidden for a bank to have simply a username-password authentication.