The formula fee = 0.0005 * max(1, (size(tx) / 1000) is the one used by the satoshi client for tx that are not using "old" inputs. However, this is not guaranteeing that you ever get into a block. It just guarantees propagation.
Oh, I think I misunderstood you. Is your software always computing a "worst case" fee, assuming all coins are fresh, even though the coins may be seasoned? If the answer is yes, then I apologise for wasting your time with stupid questions.
Yes, this is the way it works. I should probably make the fee calculation include "coin age" but it doesn't right now.
Guarantees in Bitcoin are wholy different story. Bitcoin is an implementation of worldwide Poisson-dsitributed lottery, so seeking the guarantees will be ultimately futile, sort of like a charging a premium for sale of the honest lottery ticket.
Right. However, I think that you can get close by looking at the average fees of recent transactions, and by looking at how big the pool of unconfirmed transactions is. Going forward I am pretty sure that miners will start paying more attention to transactions with higher fees. So what I am trying to achieve is to allow the user to choose between intelligent alternatives (cheap, normal, fast-track) instead of just letting the user enter an arbitrary fee.