«Cumprimentos do Brasil» é a expressão correta, e significa «mando cumprimentos do local onde me encontro, que é o Brasil». Atendendo ao sentido genérico da preposição desde, que é o de «limite a partir do qual se percorre uma extensão», não parece que o uso neste contexto se justifique.

Com efeito, a preposição desde marca geralmente «movimento ou extensão com relação a um ponto determinado no espaço, a começar de (ex.: "veio a pé desde casa"); movimento ou extensão a partir de um momento determinado, a partir de, a datar de, já, já em (ex.: "desde cedo revelou interesse"); ordem gradativa, sempre em correlação com as preposições a ou até (ex.: "estavam lá, desde ministros aos mais humildes funcionários")» (Dicionário Houaiss). Ora, sabendo que desde se faz frequentemente acompanhar das preposições até e a estejam elas implícitas ou explícitas  (ex.: «Estou à espera de um telefonema desde ontem [até hoje]»), considera-se inadequado o seu uso  como acontece na expressão apresentada.

Na verdade, se se pretende marcar apenas afastamento, sem alusão ao limite final de um percurso (cf. Textos Relacionados), emprega-se a preposição de, como no caso do envio, transmissão ou difusão de alguma coisa; exemplos: «falou do escritório» (= a partir do escritório), «trabalha de casa» (= a partir de casa), «o programa foi transmitido de Lisboa» (= a partir de Lisboa). Sendo assim, em relação ao agradecimento em questão, a forma correta corresponde a «cumprimentos do Brasil», expressão que subentende «cumprimentos enviados do Brasil».

Acrescente-se que o uso de desde em lugar de de na situação descrita não é desconhecida em textos literários portugueses, como observou Vasco Botelho de Amaral no seu Grande Dicionário de Subtilezas e Dificuldades do Idioma Português (1958):

«Em castelhano há maior emprego de desde a significar – de certo lugar. Mas temos lido em autores portugueses exemplos como este que a seguir documentamos: "Os que estavam olhando desde os muros da maldita cidade." (Vieira, Sermões, xv, 122, 1748).»