Une forme correcte devrait employer une phrase complète, et non merci de/pour
Remerciements: en général, on exprime des remerciements, pas sa gratitude (on s'adresse à une administration, ce n'est pas personnel).
Formule de politesse appuyée, notamment si on sollicite un examen particulier d'une demande:
Je vous présente mes respectueuses salutations.
Je vous prie d'accepter mes respectueuses salutations.
Je vous prie de recevoir mes salutations distinguées.
je vous prie d'agréer mes respectueuses salutations.
Formule plus appuyée encore:
Je vous prie de bien vouloir accepter mes respectueuses salutations.
Autre forme très respectueuse construite sur les précédentes:
Veuillez (agréer, recevoir, accepter, ...) ...
Formule plus courante:
Je vous présente / adresse mes remerciements.
En vous présentant mes remerciements.
Vous remerciant.
Si le service a fait preuve de vitesse / réaction particulière:
Je vous remercie pour votre diligence.
Si le service a été très sollicité et a donné beaucoup d'explications:
Je vous remercie pour votre attention / compréhension.
Si le service a particulièrement assisté:
Je vous remercie pour votre assistance.
Si le service a apporté beaucoup d'expertise:
Je vous remercie pour votre expertise / votre professionnalisme.