“Mes salutations les meilleures” makes sense, but it’s so rare (if it is used at all) that I’ve never read such a formulation in 30 years of existence. The most common form would be “Mes salutations distinguées” or “Mes sincères salutations” or even “Mes sincères salutations distinguées.”

You have to bear in mind that when you are using this kind of long and idiomatic sentences, it is always a formal, highly polite language. There’s no way it could be interpreted as too friendly.

“Cordialement” is not really colder, it’s just what we say nowadays not to sound too pompous. Mainly because the other expressions I’ve cited above have been used for so many years as THE way to end a mail in periods which required a much more formatted language that we think of them as unnaturally elaborated formulas that sound a bit hypocritical when you are only asking for, or exchanging, some basic information with an administration (or with someone you’ve never met, or a superior.)