user46123: 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?

user30668: 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. 

user5406: All full nodes process the complete blockchain. While processing, they keep a record of all Unspent Transaction Outputs in the UTXO set. For each transaction of each block the relevant changes to the UTXO set are applied: all UTXOs that get spent are removed and all transaction outputs are added as new UTXOs.
Thus, when a node has synchronized completely to the current blockchain tip, to verify whether the inputs of a transaction are spendable, they just check if for each input there is a corresponding UTXO is in their UTXO set. If there isn't, the UTXO was either spent already, or never existed.
UTXOs are unique and only can be spent once and in full. They are identified by the (unique) txid of the transaction that created the UTXO and the v_out, i.e. the position of the output in the transaction's output list.

46123: <p>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?</p>
 30668: <p>A miner does so by checking if the <code>UTXOs</code> that new transactions are trying to spend are in the <code>UTXO set</code>. </p>

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

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

<p><code>UTXOs</code> are identified by its <code>txid</code> (Little Endian representation) leaded by a <code>c</code>.</p>

<p>In the answer for this <a href="https://bitcoin.stackexchange.com/questions/51387/how-does-bitcoin-read-from-write-to-leveldb/52167#52167">question</a> you can find an extensive explanation of the format in which the UTXOs are stored, with some examples. </p>
 5406: <p>All full nodes process the complete blockchain. While processing, they keep a record of all Unspent Transaction Outputs in the <code>UTXO set</code>. For each transaction of each block the relevant changes to the <code>UTXO set</code> are applied: all <code>UTXOs</code> that get spent are removed and all transaction outputs are added as new <code>UTXOs</code>.</p>

<p>Thus, when a node has synchronized completely to the current blockchain tip, to verify whether the inputs of a transaction are spendable, they just check if for each input there is a corresponding <code>UTXO</code> is in their <code>UTXO set</code>. If there isn't, the <code>UTXO</code> was either spent already, or never existed.</p>

<p><code>UTXOs</code> are unique and only can be spent once and in full. They are identified by the (unique) <code>txid</code> of the transaction that created the <code>UTXO</code> and the <code>v_out</code>, i.e. the position of the output in the transaction's output list.</p>
