I know that this topic can create a lot of heat, but let's be the fist forum on the internet that actually might answer this conclusively.
We were doing a course today and a part of the course was a 'cover letter.' What struck me immediately was that it had no punctuation mark after the 'Dear Mr. Smith' (even the full stop after
Mr is a matter of preference between AmE and BrE). I pointed out to the tutor that I think it's wrong to have no punctuation mark there, "There should be a comma," I said.
He praised me for the query; however, he said that there should be no punctuation mark. I was convinced that that had to be wrong. After the class dispersed, I went to him again. I said that to him that I am almost certain a comma should be placed there.
He started browsing the net for templates, and a lot of them were indeed without a punctuation mark. Some of them were punctuated with a colon (which I had also previously seen, but it always looked kinda gross to me

), and some with a comma. He never saw it punctuated with a colon; but I explained to him that I believe that colon was the American way as opposed to the British comma, and that both styles are, loosely speaking, at war.
Nevertheless, his stance was that no punctuation should be there. I told him in an amicable manner that I will find out on a linguistic forum later that day (which is now). After doing some research on the internet, I came to this conclusion — and please correct me if I am wrong:
There absolutely has to punctuation after "Dear Mr. Xxx". In BrE comma serves both formal as well as informal letters, emails.
In AmE comma serves for informal letters, emails; while a colon is put into formal letters.