I dont like the idea of putting the min fee in the hands of the receiver. Seems like that will work against the best interests of senders in the long run.
Why not try a different path of calculating the min fee like difficulty retarget. You can analyse the last 2016 blocks to find the average fee accepted per kb (which would include transactions that were included without fees) and then write that into the block as a soft recommendation that wallets could use in the UI. This way the price can vary up and down according to what people were willing to spend on fees and miners willing to accept.
I absolutely do not trust vendors to set fees. I think it has to be based on what senders are willing to pay and what miners are willing to accept.