Le Code typographique* que mes collègues correcteurs et moi-même avons utilisé pendant des décennies préconise, quand on parle de quelqu'un : Nous avons dit à M. le Maire…, M. le Ministre a déclaré…. Quand on s'adresse à quelqu'un : Je vous prie, Monsieur le Maire…, Croyez, Monsieur le Ministre… (Mais : Nous avons dit à M. le professeur Dupont…, Son Eminence le cardinal Danielou…)
Cela mérite vérification, mais il ne me semble pas que les autres codes typographiques, notamment le plus célèbre, celui de l'Imprimerie nationale**, diffèrent sur cette question. Mais Perkele a peut-être une source que je ne connais pas.

* Cet ouvrage était dû au Syndicat national des cadres et techniciens du Livre (SNCTL-CGT).
** Pour répondre à la question de Clément, on peut acheter pour 15 € sur Amazon ce Lexique des règles typographiques en usage à l'Imprimerie Nationale.

     À l'article ‹ Fonctions et titres civils ›, le Lexique de l'Imprimerie nationale dit :
     « Les noms des fonctions, charges ou titres civils, publics ou privés, administratifs ou religieux, se composent normalement en bas de casse. »
     Et à l'article ‹ Monsieur, madame, mademoiselle › :
     « Ces trois termes, qui sont des titres de civilité, suivent des règles d'emploi particulières :
     1. Ils s'abrègent, au singulier comme au pluriel, devant le nom, le prénom ou le titre des personnes dont on parle ou qu'on désigne ;
          MM. les conseillers sont en conférence avec Mr le préfet.
     2. Ils s'écrivent au long avec une initiale bas de casse :
     […]
     Quand on s'adresse à la personne (dialogues, discours, lettres, adresses) :
          Bonjour, monsieur le maire. »

     Pour information.

Bonjour.

On doit donc écrire :

-  Je vous prie d'agréer, Monsieur le Maire, mes respectueuses salutations...

-  Je vous prie d'agréer, Monsieur le maire de Paris, mes respectueuses salutations...

-  Nous avons demandé à  Monsieur le maire Delanoé de bien vouloir...

Est-ce  bien cela, s'il vous plaît ?

Comment peut-on être inattentif au point de remplacer, dans le texte du Lexique des règles typographiques en usage à l'Imprimerie nationale, « MM. les conseillers sont en conférence avec M. le préfet. » par « MM. les conseillers sont en conférence avec Mr le préfet. » ? 

Je pars d'une situation où il serait question d'un maire cité parmi d'autres également nommés.

J'ai déjà vu des inscriptions telles que Nous avons demandé à Monsieur le préfet Untel et je m'appuyais sur elles pour mon exemple.

Je la connais sous une forme légèrement différente:

La vôtre convient mieux au sujet, mais de toute façon, ce conscrit-là du Languedô devait plutôt parler occitan en 1810.

http://www.youtube.com/watch?v=2FVaaKpVBSQ

En cliquant sur le lien qui se cache sous votre intervention, on s'aperçoit qu'il s'agit d'un site personnel dont l'auteur, M. Jacques Poitou, n'est pas une autorité en matière de typographie. Il est amusant, par exemple, de voir comment il s'interroge à propos de la majuscule à « le Général » (quand il s'agit de De Gaulle) ou à « le Maréchal » (s'agissant de Pétain). Comme il ignore apparemment le traitement typographique de l'antonomase, il aurait pu évoquer aussi le Rocher ou l'Hexagone.
Il y aurait beaucoup à dire sur les règles typographiques en vigueur chez M. Poitou, mais toujours est-il qu'il écrit ceci :
        Quand on ne s'adresse pas à la personne, pas de majuscule au titre.
        le (là il l'oublie, la majuscule, pourtant indispensable !) président de l'université de
        Lausanne, le professeur Tournesol, le maréchal Joukov, le docteur Max Hilaire, l'abbé
        Pierre, mademoiselle Cunégonde, le président Mao, le roi Dagobert, le maire de
        Montcuq
Et qu'aucun de ces exemples ne répond à la question de Clément, qui était : En  présence de  Monsieur le Maire de (nom de la  ville)", doit-on écrire *M*onsieur  avec un  M majuscule et *M*aire également avec  un *M* majuscule ?
Cela dit, le site de M. Poitou est très intéressant et d'une très grande richesse. On y découvre, par exemple, un texte d'Alphonse Allais écrit en langage SMS en… 1900 !

Dans l'exemple de Perkele (suscription) et dans ceux d'Ysaur (formule de politesse), nous avons affaire à des formules respectueuses qui imposent la capitale à Monsieur, Madame, Mademoiselle, écrits « au long », et la capitale également au titre quand il y en a un, d'où, dans les trois cas : Monsieur le Maire. Je crois que tous les codes s'accordent sur ce point.

En revanche, dans un texte « normal », il y a des différences d'un code à un autre.
Ainsi, comme le dit Diconoma, le code de l'Imprimerie nationale professe ceci :
          ‹ Monsieur, madame, mademoiselle › :
          […] 1. Ils s'abrègent, au singulier comme au pluriel, devant le nom, le prénom ou
          le titre des personnes dont on parle ou qu'on désigne ;
          MM. les conseillers sont en conférence avec M. le préfet.
Alors que mon vieux code typo dit :
          MM. les Conseillers sont en conférence avec M. le Préfet.

De même, le code de l'I.N., cité par Diconoma, dit :
          2. Ils s'écrivent au long avec une initiale bas de casse :
          […]
          Quand on s'adresse à la personne (dialogues, discours, lettres, adresses) :
          Bonjour, monsieur le maire.
Alors que mon code dit :
          Bonjour, monsieur le Maire (et non Monsieur le Maire comme je l'ai écrit par erreur ci-dessus, dans ma première intervention).