So it really doesn't do any hard to have TOTP enabled as a fallback if you never store the key anywhere.
They have relatively tiny key space (generally 6 digits), so if the provider doesn’t protect against brute-force, it’s quick and easy to slam the whole key space until you win.
They also need the secret in a reversible format, since the service provider has to use the secret to calculate valid codes. So the most common password brute-forcing pathway (theft of a database full of password hashes) is rendered moot: you don’t have to brute-force the hashes because they aren’t hashes, they’re just secrets. At best, the TOTP seeds are encrypted at rest, but since whatever server validates tokens has to decrypt them to do so, most implementations in the wild either don’t encrypt or keep the decryption key right next to the data.
Everything is fed into an HMAC after all. It's only the last step where truncation occurs.
The probability of guessing the challenge _wrong_ once is (1 - (100 / 1000000)). Every 30 seconds you get another chance. The probability of guessing the challenge wrong N times in a row is (1 - (100/1000000)) ^ N. Around chance number 7000, the probability that you've guessed it wrong all N times goes lower than 50/50. ~7000 * 30s in hours is around 58 hours.