Absolutely, but it's not what I'm suggesting.

Problem is, you can't attempt a TX without estimating the fee, and if the fee estimate is wrong (as in, you actually have enough) you still can't complete the TX.

My proposal would be to make it explicit that it's just an estimate, but allow the TX to be attempted. I'd rather a failed TX than one that would go through but doesn't because it was conditioned on an estimate that was wrong to begin with.