Why would you assume that the widgets are the same price and that customers expect to be able to simply “swap” them out?

I’ve never heard of any online store doing a straight swap like this. Not even Amazon. The process should be as follows:

1. Receive a request to swap the widgets
2. Check whether the order has been dispatched yet
3. Thank the customer for their time and explain the process to them
4. Process a refund on the first order and use Shopify’s refund feature to restock the item
5. Create a new order for the customer with WidgetB and email them an invoice with a link to pay online

The Widget.com accountants can use Xero or another alternative to manage the accounting. Pulling 50k orders into Xero would be fine if you upgraded to Shopify Plus.

If the Warehouse team are struggling, they could use Shippo, ShipStation, StitchLabs, Ordoro or SkuVault to manage this.