But why does the fork have to make the existing outputs unspendable? I know it is possible to make any sort of fork, but who is proposing anything that would make these locktime tx unspendable?
The actual fork under discussion has this property. Restricting all transactions to 1MB would prevent the O(N
2) part of the hashing problem.
Even better would be to restrict transactions to 100kB. As I understand it, core already considers transactions above 100kB as non-standard.
The benefit of restricting transactions to 100kB should improve things by a factor of 100 (assuming O(N
2)). The problem with doing that is locked transactions. There could be a locked 200kB transaction that spends some outputs and where an alternative transaction can no longer be created (private keys lost and/or multisig outputs).
A soft fork which restricted transactions to 100kB unless the height is evenly divisible by 100 would be a reasonable compromise here. Locked transactions can still be spent, but only in every 100th block. Mostly likely nobody has 100kB+ locked transactions anyway.