First of all, please note that the usage "Mr. Firstname" or "Miss Firstname", as in your example, are conventional only in specific subcultures of English speakers; I encountered it for the first time when I was working with prison inmates. (I am unaware of any community of English speakers that would utter "Mrs. Firstname".)
Properly speaking, which is to say in formal English, "Mr" and "Ms" (and "Miss" and "Mrs") are all applied to last names, or full names. So "Mr. Smith" is fine. "Mr. John Smith" is fine. "Mr. John" is really weird unless you are in some parts of the American South, and even then, I'm not sure you'd address a letter that way in a business context.
Second of all, part of why it feels weird is that in your example you address a woman as "Mrs." At least in the US, one does not ever address a woman as "Mrs." in a business context unless she has specifically indicated that it's her preferred title (same rules as "Capt." and "Rev.") precisely because it refers to her marital status. The reason it feels weird to address a man and a woman that way when they're not married is that the "Mrs" title is explicitly making a comment about her being married. That is why using "Mrs." is considered gauche in the workplace. Same with "Miss".
The professional default title one uses for a woman is "Ms." and she is addressed "Madam" (parallel to "Mr."/"Sir"). You may find that
Dear Mr. Wu and Ms. Smith
feels a lot less weird.
Should you find yourself needing to use "Mrs." (say, in a social context, like writing wedding invitations), there's a whole archaic set of rules for its correct use, about which I am very hazy. (Something like if Jane Doe marries John Smith, she's Mrs. John Smith but not Mrs. Jane Smith? I remember it was non-obvious and complicated.) Refer to an etiquette manual.
Frankly, the correct rules for deploying "Mrs." were complicated enough, that was what drove the widespread adoption of "Ms." which works just like "Mr."