If the punishment for not including a high enough fee is literally locking the coins in that transaction, then there is no way to determine - for a sender - how low a fee he can include.
This will, of course, make accepting unconfirmed transactions more risky, but I think accepting these is bad practice anyway, and the negative consequences of not being able to determine the lowest possible fee is worse than being somewhat able to rely on unconfirmed transactions - which were never reliable in the first place.
At some point I think the Satoshi client will need to implement this, since when mining competition increases, miners who see two transactions spending the same output will have financial incentive to include the one with the highest fees, regardless of if this transaction was sent out later. The miners trying to make unconfirmed transactions more reliable, by not including the same transaction with a higher fee if it is seen later, will lose revenue compared to the other miners, and will have a harder time staying in business.