I think you just answered your own question, sort of: simply don't decrease below the lowest threshold ever seen in a valid block. (Whether that block is in the main chain or otherwise!)
This is absolutely the same flawed idea as we have now. You can build a long chain started from the genesis block and each solution in a chain will be slow and far from optimal.