They could do what Authy does. Codes are backed up to the cloud, so you're not completely fucked if the phone is stolen. But the backup is encrypted, and to access it on a replacement device you must enter the backup password.
I suspect that this sort of issue is the real reason for making it difficult to not back up secrets to the cloud. On the one hand, you will have some number of people pissed off because they were taken advantage of and they realize that it was enabled by having backups in the cloud. On the other, you have people pissed off because they couldn't manage the final step in keeping their shit secure and are now locked out of something. The number in the latter category is vastly larger than the number in the former.
