(the title may be a little confusing, but this really is an edge case).
When checking out with a payment method which doesn't cover the whole order total (i.e. a GiftCertificate) and, once paid with the first payment method, going back to the first step of the checkout process, the shipping address is deleted and replaced with the billing address.
This happens because: 1) When paying a remaining balance on an order, the cart is set to non-shippable. This behaviour is correct, because it prevents the total to be changed. 2) When a cart isn't shippable and the "Checkout step 1" form is submitted, the "copy_address" form field is automatically set to True. This behaviour is correct (or better, irrelevant) for real non-shippable orders (e.g. ones containing only downloadable products), but is buggy if the products have to be shipped to a different address than the billing one.
There are different solutions to the problematic: 1) Add an additional attribute to the Cart object which tells wether the shipping method can be modified: 2) Simply check when setting "copy_address" to True that a shipping address is not defined yet.
I would go with the second one (will submit a pull request shortly), but I'm open to any thoughts.