I see three ways to handle that problem.

Firstly, it is worth to note that fee values will barely depend on current transaction volume and mostly on hardware, network and electricity prices, which should be quite stable. Therefore if you pay higher fee, like 1.3 of the normal value, you should achieve a high level of probability that your transaction will enter the blockchain. A caveat of this approach is that while fees may be stable when denominated in fiat currencies, the price of BlackCoin itself may fluctuate. To protect himself from an event of a sudden collapse, one may want to pay even higher fees, like 2 or 3 times the normal value.

Economically, this problem is quite reasonable: if you were to prepare a cheque to pay for any other commodity (like a TV) with a monthly advance, then this would lead either to paying too much (and therefore losing money) or not paying enough (and the purchase not occuring).

Another approach is to generate multiple versions of the same transaction which would differ only by the fees paid. This shouldn’t involve much more complexity on the client side and would even allow constructing chains of transactions. When submitting a chain, one with a most accurate fee level can be chosen (I assume the price will be the same for all transactions in a particular chain, as they will presumably be stored in one block).

The last approach is to implement “child pays for parent” which, to simplify things, may be done in a generalized way, i.e. for a block to be valid, the sum of transaction fees paid must be greater than or equal the sum of transaction fees required.

The original proposition of dynamic minimum transaction fees can simplify relaying policy. In particular, there would be no need for the GetMinFee function to distinguish between the relaying and sending cases. However introducing “child pays for parent” would mean a step back, as there would be no way to determine whether a transaction with low fee is mineable upon receiving it. A few solutions to this problem are available:

⒈ Change binary protocol so that it allows sending a few transactions at once. (Doesn’t sound like a good idea).
⒉ Lower fee threshold when relaying.
⒊ Accept transactions with low fees into mempool conditionally and evict them if a child paying an additional fee is not received shortly after.
⒋ Ignore the transaction relaying problem altogether, implementing “child pays for parent” only as a block validation rule and assuming that the user has either to mine a relevant block himself or to find someone who does it for him.

As a starting point, I would recommend option ⒋ and consider changing the relay policy if there is a demand for that. This would not exclude usage of the first two approaches. Which one is the best for an user, depends on a particular use case.