Monsieur Schulz. Das wird immer groß geschrieben, genauso wie "Madame".

mais
un monsieur à chapeau (nom commun indéfini)
ou
...si ces messieurs veulent se donner la peine d'entrer (alors qu'il s'agit de personnes définies et présentes)

Monsieur Schmidt n'est pas un nom commun, c'est un titre.

Et encore M. Schultz quand il ne s'agit pas d'une des personnes qui liront la lettre.