If we want a non-repudiation mechanism in the protocol, we should explicitly define one rather than relying on “prima facie” assumptions. Otherwise, I would recommend not relying on the existence of a signed transaction as proof of intent to pay…
Outputs could be marked as "locked". If you are performing a zero confirmation spend, then the recipient could insist that you flag the output for them as non-reducible.
This reduces privacy since it would be obvious which output was change. If both are locked, then the fee can't be increased.
This would be information that miners could ignore though.
Creating the right incentives is hard though. Blocks could be "discouraged" if they have a double spend that is known about for a while which reduces payment for a locked output.