The procedures for doing so seemed to be unnecessarily complicated and difficult to find when starting, ironically, from a Google search on another device.

Worse, the security policies seemed to be fundamentally flawed, because they kept insisting on some form of authentication based on a trusted device when the purpose of the transaction was to notify them that the trusted device had been stolen.

There has been an unhealthy trend recently of assuming that everyone has a mobile phone and that communications to that phone/number are a good method of authentication, without adequate thought to what happens if the physical device and/or the associated phone number are compromised, or to whether protocols like SMS are really suitable for this sort of application. And some of the really important things, like banks and government services and email providers (which are in practice a gateway to everything else you do online) are often among the worst offenders. I don't know what to do about this, but certainly raising awareness of this kind of problem would be a good start.