Maybe to avoid the issue with the user having to actively check for challenges, you can only allow challenges if the account is inactive (no deposits or withdrawals in the last x days). Then as a user, you could set up something which would automatically deposit money into your account/wallet periodically (or just send your income there regularly), and if you ever need to recover your account, stop all deposits to the account and wait a few days.
You could have some minimum amount, so you have to have $100 deposited in the last week, making it prohibitively expensive to DOS, but still work for accounts you are actively using. I don't think there would be much incentive to DOS someone anyways, you would have to know that they lost their password for it to be effective.
Maybe that does limit the potential uses for accounts though. Long term cold wallets like exchanges wouldn't generally have lots of in and out flows for example or people using the coin in poor countries might never have a total in/out flow of $100 despite using a coin for most of their daily life.
