Sales orders have old Bin locations after bins updated with new physical locations

I've found different results on how to be setup bins and locations but what matters is what it currently is setup, and if we need to change moving that way.

Currently we have a location as Shipping: and Bins are shelf numbers and rows. We rearrange the room for new products and move everything every few years. We update the bin locations with the item reclass journal after they have been physically moved. What ends up happening is the Sales Order now has the wrong bin location.

When the Sales Order is billed it cannot because the bin no longer has any stock. Items are only in a single bin at each location marked as the default bin.

How do we update the bin in a sales order without going line by line? Doing 1 sales order at a time would be a huge improvement but being able to bulk do it through a journal or every open sales order would be even better. Bin Mandatory is checked. Version of Navision is 2009R2 Classic. This currently is a very manual process and I feel it should be something simple.