I think that this problem is generated by a poor fee estimator in some cases, but in others i think that it is a problem of a really bad developer or business policies.
Bitcoin transaction fee estimators give you estimations that are not 100% in accuracy. Basically, estimations are not exact numbers for actual things and with instinct of mempools which can be changed very quickly by on-chain demands, you have to consider carefully from estimations and recommended fee rates, then decide what is a fee rate you want to use.
If fee rate recommended is small different than what best fee rate you check manually, I think it is good enough.
But in any case, if you need to make a RBF or a FullRBF Transaction you only need to increment your Fee by 1 sat/vB
You can still maximize your transaction chance to get confirmation but with increments like 1.1 sat/vbyte or 2.1 sat/vbyte which can make bigger difference than 1 sat/vbyte or 2 sat/vbyte as chance will be bigger and you can still save more satoshi.