I think that the long-term solution will have to be allowing transactions to be cancelled and resent with a higher fee. Hardcoded fees fall out of date (and aren't free-market), but I think that it'll always be possible for miners to trick automatic fee calculators into paying more than necessary. So it should be left mostly up to the users to figure out an appropriate fee with trial and error. Transaction cancellation is extremely difficult to add to Bitcoin-Qt, though, so this probably won't happen in 0.9. I don't think that Gavin's fee calculator will be included, either. Fees will probably remain hardcoded for now.