A wallet cannot have a negative balance, therefore your proposed solution is probably the best decentralized solution available. In order for Bitcoin to process recurring payments bitcoind would have to allow escrow-like transactions, as you've stated, where you set aside a certain amount of BTC to be released in incremental payments.
HOWEVER, in order to ensure your wallet has enough BTC remaining to fulfill these payments would mean you would be unable to spend any of the BTC locked in escrow. Perhaps there are uses for such a mechanic, I do not know. For the scenarios you have listed it seems that you might as well pay the other party a lump sum for their service instead of paying them incrementally since they have essentially the same effect on your wallet (X amount less BTC to spend). Furthermore, if you had a scenario where such an escrow service would be necessary, Bitcoin's volatile exchange rates would likely lead to issues--are we locking in a BTC rate or a BTC to USD rate? Such a service would likely end with at least one dissatisfied party.
tl;dr: The only proper solution here is to pay a BTC lump sum. You will never be able to purchase gasoline without putting your trust in the company. For all you know they just filled your car up with water!
>I don't view trusting a B&M as an issue.
I imagine that someone accepting bitcoin for their services would understand the volatility of bitcoin pricing, as they would probably just hold the bitcoin anyhow. However of course it could always be handled so that it converts to fiat upon entering escrow, then convert back on request by the acceptee.