"Cher Monsieur," est une formule correcte, mais qui sous-entend une certaine familiarité doublée de respect. Cette formule convient par exemple pour s'adresser à un client avec lequel il y a eu au minimum un contact personnel (par exemple une séance) et pour autant qu'il ait de l'estime pour la personne à laquelle l'on s'adresse. Autrement, cette formule serait hypocrite.
"Monsieur," est de loin la formule la plus courante dans les correspondances formelles de toutes sortes. ("Madame," si l'on s'adresse à une femme.)
Il y a une sorte d'assèchement des relations humaines qui fait que par autocensure, "Cher Monsieur," autrefois courant, tend à se faire rare, étant remplacé par la formule plus neutre et plus sèche "Monsieur,". Personnellement, j'utilise encore "Cher Monsieur," lorsque cela est possible, mais avec circonspection.
"Monsieur Nom_de_famille," est une formule que l'on rencontre de plus en plus en Suisse. Ce n'est clairement pas du bon français et sonne très suisse-allemand (ou anglais). Cette formule vient d'autres langues commme l'allemand où montrer que l'on se souvient du nom de la personne est une marque de politesse: "Sehr geehrter Herr Schmidt, ..."
Une autre raison pour laquelle cette formule est utilisée dans les relations commerciales est que cela "personnalise" la relation.
"Cher Monsieur Nom_de_famille" ne sonne clairement pas français, mais l'on rencontre parfois ce genre de formule pour les mêmes raisons que dans dans le cas précédent.
Quant à Monsieur suivi du prénom, cela fait penser que la personne désignée est un maquereau ou une maquerelle (un homme ou une femme qui débauche et prostitue les femmes dont il/elle tire des revenus).