So somewhere in the customization of the ordering process, is where the issue lies.
it is probably when selecting shipping addresses that the problem occurs or somewhere else down the line.
In reality, this sort of shipping address selection is not intended for use with Paypal express Checkout.
With Express checkout, the user goes to the paypal site. they enter the billing and shipping address there and they are then directed to your site to either cancel or process the the order.
The shipping address is set on paypals site and should not be changed after words.
if you wanted to create the type of system you are talking about, you should be using Payments pro, not express checkout.