When users pay too low a fee, they should:

1) See immediate failure as they do now with fees that fail to propagate.

2) If the fee lower than it should be but not terminal, they should see degraded performance, long delays in confirmation, but eventual success. This will encourage them to pay higher fees in future.

The worst of all worlds would be to have transactions propagate, hang in limbo for days, and then fail. This is the most important scenario to avoid. Increasing the 1Mb block size limit I think is the simplest way to avoid this least desirable scenario for the immediate future.

We can play around with improved transaction selection for blocks and encourage miners to adopt it to discourage low fees and create fee pressure. These could involve hybrid priority/fee selection so low fee transactions see degraded performance instead of failure. This would be the conservative low risk approach.