one of the aspects of the cost for the bitcoin network of a transaction, which is currently not taken into account in the default fee policy, is the permanent storage cost it requires. The size of a transaction is used, but not whether or not it will ever be possible to prune it from the chain.
It is possible to compensate for this, by giving a "bonus" for the redeeming of earlier txouts. If a transaction is large, but has a lot of 0.01 BTC inputs, and one big 10 BTC output, its cost for the network may actually be negative, since it may allow many older tx's to be pruned in the future.
Use a term A*(nTxOut - nTxIn) in the fee calculation.
This simply gives a bonus to transactions that merge a lot of coins, and a malus to transactions that split a lot of coins.
Do some weighing based on the value of the produced/consumed txout's, as small coins are worse for the network than large ones.
Use a term B*(sum(2log(21M/txout.amount),txout in tx.outputs) - sum(2log(21M/txin.amount),txin in tx.inputs)) in the fee calculation.
Essentially, we define a "weight" to each coin (=unredeemed txout), defined as the 2log of its fraction of the maximum amount. A 1 BTC coin would weigh 24.32, 1 ucBTC would weigh 50.90.
Splitting off 0.01 BTC from a 1 BTC coin, would increase the total weight of coins with 30.98, merging 100 coins of 0.01 BTC into a 1 BTC coin decreases the weight by 3072.45.
Use the actual sizes in the calculation.
Use a term (tx.size - C*sum(txin.prevout.tx.size/txin.prevout.tx.outputs.count, txin in tx.inputs)) instead of the normal per-size fee.
Essentially, we subtract a fraction of the size of all the prevout tx's from the current one. C should be between 0 and 1. C=0 is the current scheme, with C=1 a simple transfer-entirely transaction in a chain typically becomes costless (at least what its size concerns, there may and maybe should be other fee factors).