On ne dit pas : nous vous remercions de la confiance dont vous nous avez témoigné, car on se trompe.
C'est vous qui employez la tournure correcte.
Marina Yaguello, dont il est question dans une autre rubrique, et divers linguistes, l'ont noté : les francophones ne savent plus se servir des pronoms relatifs, ils mettent que dans toutes les positions, même là où il n'a que faire.

Félicitations pour votre maîtrise de ce point difficile !

Tout à fait, gb, le verbe témoigner a deux constructions,
une construction transitive directe, témoigner,
et une construction intransitive, témoigner de.

Si l'on fait le choix de la construction transitive (pour laquelle Robert donne l'exemple suivant : « Je lui ai témoigné de la froideur... », comprenne qui pourra !), le relatif est que.
Si l'on fait le choix de la construction intransitive, (exemple de Robert : témoigner de sa vigilance), le relatif est dont.

Notre aimable correspondante a fait le choix de la construction intransitive, elle doit donc employer dont.
Mais elle pourrait dire : nous vous remercions pour la confiance que vous nous témoignez.

ABSOLUMENT PAS! c'est même là que les ennuis pourraient commencer.
On témoigne ses sentiments à quelqu'un nous dit le Petit Robert: I TÉMOIGNER  verbe transitif direct -2. Exprimer, faire connaître, faire paraître...
On témoigne sa confiance à quelqu'un. Remplacez témoigner  par exprimer, vous allez voir que tout s'éclaire.

Parce que si on remplace, dans cette tournure erronée,  témoigner par exprimer, on a:
«nous vous remercions de la confiance dont vous nous avez exprimée». Pas joli, non?

En revanche:
«Nous vous remercions de la confiance que vous nous avez exprimée.»
«Nous vous remercions de la confiance que vous nous avez témoignée.»
L'accord du participe en devient évident et la phrase que cite Catherine est grammaticalement juste.

II TÉMOIGNER V. tr. ind. TÉMOIGNER DE: confirmer la vérité, la valeur de (qqch.) par des paroles, des déclarations.... Il était d'accord, je peux en témoigner. Amha, il n'y a pas vraiment d'alternative entre les deux acceptions I-2 et II de  ce verbe  qu'il convient de manier prudemment, comme tout ce qui touche au témoignage.

Tout l'art du français consiste à masquer le défaut de maîtrise de ses subtilités.
Personnellement, je dirais : en vous remerciant de votre confiance !
De même, j'utilise souvent la plus courte des formules de politesse :
Cordialement.

Dont témoignait votre réponse, parce que celle-ci est parfaite!

Bien que j'acquiesce totalement à la teneur générale de votre propos, chère Orientale (quel hasard! vous êtes de mon avis quant à la justesse de "Nous vous remercions de la confiance que vous nous avez témoignée"), le problème n'est pas, amha, «la présence intrigante de "de" dans bien des constructions transitives directes du français» mais, comme souvent, la surabondance d'homophonies. Que n'avons-nous, pour tout simplifier, une langue avec des tons!:D:D:D

Au risque de mal l'interpréter, je crois que BP a voulu dire ici que la difficulté est que «de» se prononce en français de la même façon quel que soit son rôle, sa nature ou sa fonction, alors que les langues à ton auraient l'avantage de faire entendre les différences.
Pas encore trouvé de jeu de mots