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.

Drak