I think Alex's approach is better; I don't think we can know how much better until we have a functioning fee market.
We don't have a functioning fee market now, because fees are hard-coded. So we get "pay the hard-coded fee and you'll get confirmed in one or two or three blocks, depending on which miners mine the next three blocks and what time of day it is."
git HEAD code says you need a fee of 10,0000 satoshis/kb to be pretty sure you'll get confirmed in the next block. That looks about right with Alex's real-world data (if we take "90% chance" as 'pretty sure you'll get confirmed'):
My only concern with Alex's code is that it takes much longer to get 'primed' -- Alex, if I started with no data about fees, how long would it take to be able to get enough data for a reasonable estimate of "what is the least I can pay and still be 90% sure I get confirmed in 20 blocks" ? Hours? Days? Weeks?