Don't have all the answers for you at this moment... I think I've been tossing ideas around in my head for what to do with addresses for a couple months now. One thing I would say is that it would be fairly trivial for a module to define custom checkout panes that load and store data for addresses in a different DB table and uses hook_order() to populate the order object with that data later on.

I guess ideally addresses would be stored in their own table and the individual order table, so you could alter an order's address however you need without affecting the other addresses but could also populate address fields from the stored address list. But like I said, haven't moved passed the brainstorming phase to make up a game plan for the changes.