Seeing as there are less Bitcoin with no transaction history, these are very rare.  I would assume a 20-25% premium is in the right range?

The buyer would have a trail from "no transaction history" to their wallet address.  Technically, the only history would be to their wallets address.