Thought I'd give this thread a mega-bump just because I'd still like my mockup to magically come true (some fee guesstimation work is in progress for 0.9). I recently tried to export particular private keys into a new wallet, even calculated in Excel using UTXO, and still ended up with an unspent dust that wasn't grabbed out of my wallet thanks to the opaque fee calculations in Bitcoin-Qt.
Comments invited, from those who intimately know what Bitcoin already does.
isn't it better to look at the current pool of transactions, and check what fee would be required to get the transaction above a certain percentile?
This is generally what I was indicating in my mockup where "network statistics" are listed. With current statistics it might look like:
1181 transactions currently pending on Bitcoin network
Recommended additional fee: 0.00030 (0.00015 per kb)
With the current fee, this transaction would rank below 171 pending transactions
Since the local client won't know all transactions miners could be considering, and it's hard to educate about block variance, being non-specific but informative about the estimated time is hard. A "percentile" might not be accurate, because a lot of what's pending is a big backlog of zero-fee junk that will take many blocks of 27k priority-based space to clear.
Fee
per kB is actually more important than total fee, the mockup should indicate "Per kB" optional fee, just like Bitcoin-Qt does now, and then calculate total fee amount live.