A transaction that has been included in a block does not need to be in a node's mempool in order for that node to validate the block. Each block contains the transactions, so by downloading and validating a block, the node will have received a copy of all transactions in it (so that it can validate the transactions, as part of validating the block).
As you mentioned, there would otherwise be problems syncing old blocks, because the transactions in those blocks would be invalid if you tried to add them to the mempool today (because their inputs have already been spent!).
Further, a miner can include a transaction in a block, without having ever broadcast that transaction to the network otherwise. So in that case, no other node would ever have included the miner's transaction in their mempool!
Note that compact blocks (BIP 152) is an improvement to the block-relaying process, that allows nodes to compare a new block's transactions to their local mempool, and thus avoid having to re-download transactions they already know about.