How to verify virgin bitcoin I am willing to acquire bitcoin without transaction history (virgin bitcoin) at a premium. How do I tell that the bitcoins I receive do not have any prior transactions (except of the mining one)? What proof would the counterparty need to provide?
There is only way way to acquire Bitcoin without a previous utxo associated with them: Mine them.

You could pay a miner to mine directly to an address that you control, if you don't have the hashpower yourself.

If you pay someone else who transfers such coins to you, you've already destroyed the value as the act of transferring them will move then from the coinbase (mining output) utxo to your own address, which will be a regular utxo just like any other on the chain.

Verification is easy - just look at the transaction that sends the Bitcoin to you, and verify that it has only one input referencing a 0-hash previous output. When verifying with Bitcoin Core, this will be parsed as a coinbase input. For example, for the latest coinbase tx at time of writing, Bitcoin Core produces the following output (truncated for :

{
  "txid": "21429071642d1838aaaa24b0b5cd5868934952424c9dacd5f63f7f900a416755",
  "hash": "9985102431de97ee3b0cf4e9631daa85a48b84e6476d38998018b268ab27cf99",
  ....
  "vin": [
    {
      "coinbase": "03c13109049f73c25d434e2f54545454545431313131fabe6d6da23d1eb317523b78d2e61f76e493dde0a8f87cd83c585f8bce158d107bf5047c010000004204cb9a8102498456268a5d0aec1c00",
      "sequence": 4294967295
    }
  ],
  "vout": [
   ...
  ],
  "hex": "020000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff4e03c13109049f73c25d434e2f54545454545431313131fabe6d6da23d1eb317523b78d2e61f76e493dde0a8f87cd83c585f8bce158d107bf5047c010000004204cb9a8102498456268a5d0aec1c00ffffffff036f65524b0000000017a914f870b7fbb0ce391d9ddc16ad98479d8cbbbd5c41870000000000000000266a24aa21a9ed70b3372921878104277c3e0697fc079b2152d4c2aab2a1c653387f93f416b3290000000000000000266a24b9e11b6da4a898ffc213ffe4708753951bcafa58fcd7d1b9149f39b5c74dc1e1a48b21100120000000000000000000000000000000000000000000000000000000000000000000000000",
  "blockhash": "00000000000000000006d147b5ecfc60100ca2b206240929ffa3f594dae95e08",
  "confirmations": 1,
  "time": 1573024670,
  "blocktime": 1573024670
}