Wouldn't you only need to verify proof-of-work on the largest chain? Largest meaning the highest cumulative difficulty rather than number of blocks.

If you include a timestamp in each block, just have each node simply reject times that are out of order or too far from the current time, which will prevent people from mining on an invalid chain. "Current time" meaning nothing more than a few minutes in the future of now. Yes, even when dealing with an old chain.

Here is how it works:

If an invalid or malicious person spends hashrate to mine a block with a bad date, all the nodes in the network will see it and reject the block.

Because the block is rejected, everyone else keeps attempting to mine the same block, but with the correct timestamp. The window is: greater than the last block, less than a couple minutes from now.

Because most miners are on non-malicious nodes, they eventually produce a longer chain than the chain with the bad timestamp.

Because this good chain is longer, new nodes that sync the blockchain from scratch would simply pick the longest of the available chains (which is the good one).

This could still go wrong if the attacker has a large amount of hashrate (or luck) for an extended period of time, but this gets very expensive very fast. This is why it is sometimes good to wait a few blocks before assuming consensus.