I propose the old chain actually keeps a record of legacy transactions, and that the new chain effectively becomes a sidechain (of sorts).

Do two-way peg using spend-all coins (like SW) in the original chain. So new transactions can actually send coins to legacy addresses.

I assume SW is not yet implemented, so that's why I simply copy some SW tricks.

1. A transaction is send to a spend-all address (legacy chain), segregated witness data is added to the segregated block (like SW).
1. Transactions to/from segregated addresses only go into the segregated chain
1. When creating a transactions to legacy addresses a transaction is created from any spend-all transaction (legacy chain) and coins are destroyed (on the segregated chain)

Miners would then simply check whether all spend-all transactions in the legacy actually came from "destroyed" coins in the new chain.