Same as with PoW. You can't know with certainty that one spent millions of dollars to find a valid hash, but you can easily assume it's true, and you'll be right. One ought to spend millions, on average, to accomplish that.
It's realistically impossible to find a valid Proof-of-Work without the work.
I understand the point you are making, but your analogy isn't a great one. Occasionally someone
does find a block without doing the work, as we see when an empty block is mined within a few seconds of the preceding block. The amount of work done to find such a block is only a very small fraction of the average amount of work done across all blocks at a similar difficulty. So sometimes you
do find a valid solution without doing (much of) the work.
Further, sometimes you'll see a miner with the hash power of just a single ASIC finding a block. Multiple such examples here:
https://bitcoinmagazine.com/markets/third-solo-bitcoin-miner-finds-valid-block. So sometimes you
do find a valid solution without spending millions of dollars.
The chance of these things happening is small, but not zero. The chance of someone knowing the private key to 1BitcoinEaterAddressDontSendf59kuE is exponentially smaller, but is still not zero.