Looks like the issue is actually that the shipping address (and its zip code) only gets saved when the Sales Order is saved. But the calculation of the shipping cost is getting calculated prior to this. So what happens is no Ship To Zip Code is considered for the calculation. Automatic calculation of shipping cost is done when there is a chosen Shipping Method in the Sales Order. So what I did was set the Shipping Method to null, save the Sales Order then go back and update the Shipping Method on the created SO so that it'll calculate the correct Shipping Cost.