Does a new block necessarily include all transactions that occurred before its generation? What about network latency? 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?
Miners have total freedom to choose which transactions they will include in their blocks. Most miners will include any transaction that reaches them (assuming it includes an appropriate fee) but nothing forces them to do so.

But if a miner decides, for whatever reason, to omit a particular transaction, or if it's omitted by an accident of timing, no permanent harm is done. Another miner can include that transaction in a later block with no problem. Transactions don't even have a timestamp, per se, so it's not a problem if it takes a long time (other than the inconvenience to the parties involved). (Blockchain.info and its ilk may record the time at which they first saw the transaction on the network, but that time stamp isn't part of the transaction itself, as far as I know.)