If Alice knows enough to see that she needs CHECKBLOCKATHEIGHT to avoid paying Bob twice, then she also knows that Fred owes her 4BTC. If Bob complains about getting paid faster, Alice can let him know that Fred essentially stole his coins and that when she is certain he (and she) can't get them back, she will send a different four coins to Bob. If she can establish trust with Bob (She'd trust Bob to pay her back if he gets back the coins Fred stole), then she can pay him again. Bob could also make a transaction to send the first input from Alice back to her (since he doesn't have those coins anyway), sign it, and send that to her. She can then keep it instead of having to use the new opcode.
Or she can let her wallet use the new opcode so that the logic is built in, if we add this opcode. Wallet makers who want to help solve this problem can either implement the new opcode, or they can offer people like Bob the ability to refund orphaned transactions so that they can be duplicated in the valid chain without any risk to the original sender.