A once and for all solution would be to set your fee rate dynamically using "estimatefee" command.
We do use the estimatefee. However we use confirm target of 20 blocks and it doesn't always work correctly with such a high target. I see that today's transactions are getting confirmed correctly though.
Here's a payout transaction from FaucetBox that didn't get confirmed by Blockchain.info