I think that what is confusing you is the dynamic of customer vs. service personnel relationships in Japanese culture and language. The customer is and always will be in a higher position than the staff member who they are corresponding with.
That being said, it is still important to be polite and use 丁寧語. What one should try to avoid using self-deprecating language (謙譲語）and language that elevates the other party (尊敬語）. In many cases this is true whether you are corresponding with someone in a high position of authority in the company or their lowest-level employee. You, as customer, are in a position of power/authority as far as language use is concerned.
Another thing to consider is that the customer service rep will, whether consciously or not, try to be more polite and deferential in their responses than the customer. If you set the bar too high in your own use of language it can be frustrating for them to try to match/surpass your own use.
Apologies can be seen as self-deprecatory and hence a sign of meekness/contrition/surrender and corresponding loss of face. This is carried to the extreme in some relations because personnel will apologize for the slightest thing that might have caused offence, whether offence was warranted or not. 申し訳ございませんs fall out of some people's mouths so often that they carry very little meaning and can actually sound insincere. This is why some people think that such expressions can sound sarcastic, as they are often used simply to placate the other party without a genuine feeling of contrition.
I would avoid using すみません as it is too casual and 申し訳ございません/申し訳ありません as they are too contrite. Avoid ございます expressions in general in favor or です/ます forms.
Imagine the kind of person who makes a mistake that causes other inconvenience. When called on for them to recognize that they are in the wrong they just shrug it off and say, 'So I was wrong. Don't make a big deal about it.'. You want to be that asshole.
遅く 問い合わせて 申し訳ございませんが,
Your request is not a 問い合わせ, which is more of a simple inquiry/request for information. Also, when you 'apologize' for responding belatedly you do not actually need the apology part. A simple 'お返事が遅くなりました。' will work. It shows recognition but not contrition.
This sounds like you are saying it was their mistake.
You are asking them to send it to your 'new address again' when they have not sent it to the 'new address' once. ぜひ shouldn't be used here as it presumes that they have agreed to re-send the item or diminishes the significance of the request.
It could be written as shown below:
新しい住所は：12345 Main St. Your Town, Your State, Your zip code.
The ご迷惑をお掛けしました part acknowledges the trouble that was caused without being overly apologetic.
If the circumstances behind why the wrong address was provided are different, it really makes little difference to them. The main point is that you are not at the address that the item was sent to and you can fudge the details a bit to try to get a kinder response.