Will BTC value depend on their history? It might seem that virgin coins will have higher value than older coins that have lot of exchange transactions that might make it more traceable.

Is there some prevision in the protocol for this effect?
There is none, and I don't think it will ever be significant. There is a gentleman's agreement that's part of what makes Bitcoin work that a Bitcoin is a Bitcoin is a Bitcoin.

You can have a few "rare Bitcoins" with extra value. I might pay extra to have one Bitcoin transferred to me directly from the coins in the genesis block, for example. But just like there can be a few rare dollar bills, a dollar only works as a medium of exchange if more or less, we all agree that a dollar is a dollar. A prime serial number is cool, but your grocery store can't care about that if it wants to do business.