You are correct in that tracing a transaction fee is equivalent to tracing any kind of transaction. There is no event horizon for transaction fees as implied by the article. New coins have no history because they are new, the coins for the fee are not new, they are simply added to the reward total for successfully mining them.
---
That being said the bitcoin metaphor is misleading in the details as metaphors always are. There are no bitcoins, in that there are no IDs that are kept in an inventory that represent every individual bitcoin. Instead bitcoins are represented as ledger entries only. The traceability, or lack thereof, comes from the ability to trace the ledger entries. It goes something like this:
Miner: "Everyone agrees I now have 25 bitcoins in account M1. Because I'm a winner!"
Miner: Tx :: Send 25 bitcoins from M1 account, to P2 (Person 2's public key)
Person 2: Tx :: Send 5 bitcoins from P2, to P3.
Balances
M1: 0
P2: 20
P3: 5
P3's bitcoins can be traced to P2, and then M1. Now P2 sends a transaction with a high fee (up to now no fees were paid).
Person 2: Tx :: Send 1 bitcoin from P2, to P4, with a tx fee of 19.
Miner 2: "Everyone agrees I now have 44 bitcoins in my M2 account. Because I'm a winner!"
Balances
M1: 0
P2: 0
P3: 5
P4: 1
M2: 44
M2's bitcoins can be traced to 25 new coins, 19 fee coins given by P2, who go them form m1. P3 is not involved in the transaction history, and every transaction is traceable.
---
That being said the bitcoin metaphor is misleading in the details as metaphors always are. There are no bitcoins, in that there are no IDs that are kept in an inventory that represent every individual bitcoin. Instead bitcoins are represented as ledger entries only. The traceability, or lack thereof, comes from the ability to trace the ledger entries. It goes something like this:
Miner: "Everyone agrees I now have 25 bitcoins in account M1. Because I'm a winner!"
Miner: Tx :: Send 25 bitcoins from M1 account, to P2 (Person 2's public key)
Person 2: Tx :: Send 5 bitcoins from P2, to P3.
Balances
M1: 0
P2: 20
P3: 5
P3's bitcoins can be traced to P2, and then M1. Now P2 sends a transaction with a high fee (up to now no fees were paid).
Person 2: Tx :: Send 1 bitcoin from P2, to P4, with a tx fee of 19.
Miner 2: "Everyone agrees I now have 44 bitcoins in my M2 account. Because I'm a winner!"
Balances
M1: 0
P2: 0
P3: 5
P4: 1
M2: 44
M2's bitcoins can be traced to 25 new coins, 19 fee coins given by P2, who go them form m1. P3 is not involved in the transaction history, and every transaction is traceable.