How can a miner verify that a UTXOs is not spent elsewhere? How does a miner verify that a UTXO is not spent somewhere else, wouldn't he have to search the entire blockchain from that UTXO and onwards to see if this was the case? Assuming any real scale this would effectively take ages, or am I misunderstanding something?
A miner does so by checking if the UTXOs that new transactions are trying to spend are in the UTXO set. 

The UTXO set is the collection of UTXOs that are non-spent, and therefore, can be redeemed by new transactions.

To do so, a miner (as well as any other node) checks the LevelDB database found in .bitcoin/chainstate by default in unix systems.

UTXOs are identified by its txid (Little Endian representation) leaded by a c.

In the answer for this question you can find an extensive explanation of the format in which the UTXOs are stored, with some examples.