Les usages relatifs aux genres des titres, noms de fonction, etc., dont relèvent vos deux premières questions, sont en pleine évolution sous l'influence d'un mouvement historique tendant vers l'égalité de considération des hommes et des femmes.
Plus encore que pour des faits de langue comparativement stables, il est donc difficile de parler de règle claire faisant référence pour le locuteur.
Concrètement, la tendance est à la féminisation des titres et noms de fonction. Mais il ne faut pas négliger que le genre masculin a eu fonction de genre neutre (c'est-à-dire valant pour des individus hommes et femmes) et qu'il est fort pratique de conserver une certaine proportion de formes «génériques». À mes yeux, il est donc bon de ne pas résister outre mesure à une tendance à la féminisation qui a un sens socio-politico-culturel (pour aller vite 
) tout en gardant raison, c'est-à-dire en préservant le côté pratique de la langue.
madame la présidente de la chambre des notaires (de tel département)
ou :
madame la président de la chambre des notaires
On peut choisir la première forme, mais pas la seconde, qui commet une erreur d'accord en genre entre le premier article et le titre.
Le genre de l'article découlera du choix qui sera fait pour le titre. Dans la tradition, les titres et noms de fonction ont le genre neutre et la forme du genre neutre est le genre masculin. Dans la fidélité à la tradition, on devrait dire :
Madame le Président de la Chambre des Notaires
Mais d'une part, le fait que la forme générique soit la forme masculine a pu légitimement irriter à l'époque de la «libération de la femme», et d'autre part la succession d'un mot désignant une femme et d'un article + titre au masculin est troublante pour les locuteurs (d'où vos questions, d'ailleurs). Aujourd'hui, c'est donc l'usage féminisé qui a tendance à s'imposer :
Madame la Présidente de la Chambre des Notaires
Tant qu'on y est : Pour la même femme, j'imagine qu'on ne parlera pas de maîtresse :
Chère maître ? Chère Maître ?
Cher maître ? Cher Maître ?
Oui, là, en tant que locuteur, vous ne vous posez pas de question. Les multiples sens de «maîtresse» et les connotations plus ou moins scabreuses de ces sens empêchent d'envisager, pour l'instant au moins, de féminiser la civilité correspondant au métier d'avocat ou à la qualité de professeur éminent.
Bien obligé, donc, de conserver la civilité «générique». Et pour la cohérence logique de la langue, il est préférable d'accorder l'adjectif. (On peut toutefois noter de plus en plus d'usages de mélange des genres, mais c'est une pente glissante pour la logique de la langue.) Donc :
Cher Maître
Pour finir, la formule de politesse :
"Je vous d'agréer, xxx à compléter svp xxxx, l'expression des mes sentiments mes meilleurs" peut-elle destinée à une femme ? Il parait qu'on ne donne pas ses sentiments à une femme ?
Ouh la, ce n'est même plus de la tradition, c'est du passéisme, là ! Ou alors il faut poser la question à Nadine de Rothschild et pas sur l'ABC de la langue française !
Je veux dire qu'on parle là moins de langue et plus des «bonnes manières» de la bonne société, dans laquelle on suppose qu'il était scabreux d'utiliser le mot «sentiments» dans une lettre à une femme qui n'était pas la sienne !
Au XXIe siècle, oubliez les formules longues, toute faites et compassées. Faites plus court en essayant de coller à la situation et au rapport que vous avez avec le destinataire.
Si vous tenez à utiliser une formule de clôture classique, votre insert «xxx à compléter SVP xxx» est censé reproduire exactement la formule d'ouverture, avec la même capitalisation :
Je vous prie d'agréer, Cher Maître, l'expression de mes meilleurs sentiments.
Lionel
