Suppose I'm a new node and want to verify the blockchain. How do I verify that each block was mined with the correct difficulty?

I'd need some record about the actual real-world timestamps for each block. Then I could say something like "duration between block x and block x+1 was > 10 min, so the down-adjustment in block x+5 is justified".

But if those timestamps were stored on-chain, an attacker could simply lie about them and keep difficulty artificially low on its alternative chain.

On the other hand, if we had some un-forgeable record of block timestamps, wouldn't this solve the double-spend problem all on its own? Would we even need PoW at this point?

Edit:

Ok, sibling comment seems to suggest bitcoin has solved this problem differently: https://news.ycombinator.com/item?id=29368166