Netsuite doesn’t allow (that I know of) multiple ship to addresses on Locations. Any ideas on updating the shipping address per fulfillment on a Transfer Order? Maybe pull from a custom record or something.

We do this using parent/child customer records. I don't know if that is an option for you but it works well. Each ship to is a child to the parent customer.