I read What exactly is Mining? and What are bitcoin miners really solving?, but was left wondering: What happens if a new transaction comes in, whilst mining? To answer that, I found Do transactions affect the discovery of a block?, which, if I understand correctly, says that the mining must "start over" (but the chances of finding the "nonce" on the first attempt are about the same as any subsequent attempts, so there's no "loss of work").
But, what about network latency? It must take a finite amount of time for a new transaction to reach miners—so what happens if a miner solves a block, but then receives a transaction timestamped before the block was solved?