Tout d’abord ne pas abuser de majuscules, Madame le maire-adjoint suffira. Mais, si vous lui adressez un courrier, vous écrirez Madame l’Adjointe au maire, pour suivre joelle, mais sans majuscule à maire.
Pour ma part, je reste attaché à Madame le maire. 
En effet, maire est un nom de fonction et un nom masculin.
« En ce qui concerne les titres, les grades et les fonctions, au nom de la neutralité institutionnelle et juridique qui leur est attachée, l’Académie française recommande d’éviter, dans tous les cas non consacrés par l’usage, les termes du genre dit « féminin » et de préférer les dénominations de genre non marqué [masculin]) » (Académie française).

La  féminisation autoritaire et systématique, à laquelle on assiste (on participe ?) est regrettable, car on ne décrète pas une langue, c’est l’usage qui la fait, or à l’époque (1984, 1998), l’usage ne la préconisait  pas, il a fallu un décret dommageable pour l’imposer.
Mais force est de constater que le féminin, pour les noms de fonction, tend à être généralisé et l’on ne fera pas machine arrière, l’on pourra de moins en moins s’y opposer (je « résiste » encore).
Madame la maire est de plus en plus répandu et tend à être consacré par l’usage, on écrira donc aussi bien Madame le maire-adjoint que Madame la maire-adjointe. (gare aux sensibilités).
Il est vrai, comme le fait remarquer joelle, qu’il vaut mieux écrire Madame l’Adjointe au maire.