Si c’est la question des majuscules qui est gênante (car les majuscules ont différentes fonctions : lisibilité, mise en valeur, initiale de nom propre…), on peut commencer par demander de façon plus neutre : si on écrit le nom en vert, est-ce qu’on écrit la particule en vert ? La question revient à savoir si la particule fait ou non partie du nom de famille. Du point de vue de l’état civil français, oui, la particule fait partie du nom de famille qui se transmet aux enfants. Ainsi, quand on lit :
— Nom (en majuscules) :
— Prénom(s) (dans l’ordre de l’état civil) :
la particule du nom doit être écrite dans le premier champ, et être écrite en majuscules.
C’est ce formalisme qui a cours dans l’administration française. Par exemple dans les listes de candidats publiées par le ministère de l’Intérieur, on trouve l’abréviation « M. » ou « Mme » suivie du prénom en minuscules et du nom en majuscules :
— Mme Gertrude DE REVIERS DE MAUNY
— M. Abel DE WISMES
Dans la séquence prénom + nom, il n’est pas envisageable d’écrire la particule en minuscules devant un nom en majuscules. Ainsi, on trouve sur les couvertures de livres Jean d’Ormesson, JEAN D’ORMESSON, et Jean D’ORMESSON, mais jamais Jean d’ORMESSON.
Tout ce qui précède montre que dans le formalisme « prénom + nom », la particule fait bien partie du nom.

En revanche, quand, comme dans votre exemple, on écrit « madame » sans abréviation, et sans prénom, dans le cadre d’une phrase, il n’y pas de bonne raison pour utiliser des majuscules.