Le courrier électronique a changé les règles épistolaires. Il y a seulement une trentaine d'années, lorsqu'on écrivait couramment des lettres manuscrites, on pouvait terminer une lettre un peu formelle par "je vous prie de croire à l'expression de mes sentiments les meilleurs", sauf si, de sexe masculin vous écriviez à une femme, sans essayer de la courtiser, il valait mieux, selon l'étiquette en cours à cette époque terminer par "je vous prie de croire à l'expression de ma considération distinguée", certes assez loin d'une invite.
Tout ceci n'a plus cours, mais le "sincèrement" est un anglicisme en fait employé couramment depuis toujours en anglais avec le "Sincerely yours" ou "Truly yours". Le "cordialement" ou "bien cordialement" est tout à fait français et passe partout et pour ma part, je l'utilise assez couramment. Il n'y a rien d'incongru dans le fait que la préfecture vous écrive en terminant de la sorte. Si vous souhaitez informer votre correspondant de votre reconnaissance sincère pour un service rendu, vous pouvez terminer par "avec mes remerciements les plus sincères" ou mieux "avec mes plus sincères remerciements", cette dernière formule mettant en valeur la sincérité (une denrée rare) devant la gratitude.