It could not be “to whom both”. If the clause were not a relative clause, you would write something like “I express my sincere gratitude to both of them.” You can turn it into a relative clause by replacing “them” with the relative pronoun “whom”, which needs to be “fronted”—placed at the start of the clause. But if you wrote *”whom I express my sincere gratitude to both of,” the preposition “of” would be “stranded”—something that is possible in some sentences, but not I think here. So other things move with the relative pronoun (this is called “pied-piping”). If we just moved the “of”, we would get “of whom I express my sincere gratitude to both.” This sounds a bit better to me, but I think that it still sounds worse than the option you mentioned with pier-piping of the phrase “to both of whom”—“to both of whom I express my sincere gratitude.”
Pied-piping is fairly formal, but you said that the context of the sentence is supposed to be formal.