Agree. I quite like Mark's proposal. Yes, formally it is hard fork. But the step 4) can come very far in the future, when the penetration of <0.8 clients will be mininimal.
This problem is very clearly a *bug* in the old codebase. So let's be forward thinking and do what we would do in any other situation: fix the bug, responsibly notify people and give them time to react, then move on. Let's not codify the bug in the protocol.