So I think CONAME solves 90% of this. It's set up in such a way that third party verifiers only have to check that the update counter for each key is monotonic. Users can check just that, for the current epoch, the write counter is correct and their key is there. So only a user themselves should see a warning. (and warning cans be disabled by default ... as long as the attacker doesn't know if the user has them on or not, it's an issue)

In contrast, in CONIKS, a user had to check every single epoch. Which was impractical and meant you relied on third party auditors.

This doesn't deal with the restore from backup issue. I think given the FBI apple phone issue though, maybe it's worth reevaluating the risk vs. reword here. Especially if user visible warnings are opt in.