Ce mot (madame) ne prend pas normalement de majuscule. C’est son abrébiation (Mme) qui en prend une.

Certaines majuscules portent un sens : la rue du Général Dupont (c’est le nom propre de la rue, et même parfois avec des traits d’union) / l’épée du général Dupont (le mot général n’est pas ici un nom propre).
Mais généralement non, et on écrit : je remercie le président Raffarin, le cardinal Casimir, et madame Patatras pour l’aide qu’ils m’ont apportée.
C’est ainsi qu’on dit par exemple dans un roman que le général Albert a séduit madame Bertrand sous l’œil du président Faure.

Parmi les aspects à considérer ici :
— s’agit-il d’un titre ? non (et quand bien même, cela ne jouerait pas : le duc Schwepps)
— s’agit-il d’une adresse directe à la personne ? non (et heureusement car sur ce sujet, @Tara et @chambaron s’opposent ici constamment)
— s’agit-il d’une abréviation ? non car ce n’est pas abrégé ; et cependant, en cas d’abréviation, aurait-on mis un majuscule ? oui : Mme, mais ce n’est qu’un code ; et si vous trouvez ce code illogique, vous avez raison

Si dans votre court texte introductif vous voulez remercier Mme Patatras, faites-le classiquement avec l’abréviation et la majuscule, c’est le plus fréquent ; ou en entier et sans majuscule. Selon mon approche, l’écriture sans abréviation ni majuscule est beaucoup plus incarnée, et dépasse le simple déterminant. Pour un diplôme, je vous suggère d’écrire « Mme Patatras« , et dans le roman qui exposera vos tendres relations avec cette dame d’écrire « madame Patatras« .