Working part-time in customer support, I have to deal with the same situation very often, and I often have to google for "awkward" names, too. What I usually end up with when nothing helps, is either of the following:
I just drop the "Mr/Ms" altogether. "Dear Maria Cannavaro", "Dear Wei Li", etc.
If the person is located in the US, I assume that they do not object to being addressed by their first name. "Dear Maria", "Dear Alex".
Also, I might sometimes use a simple "Hi there" or "Hi", but usually only if the person has previously contacted me using a similar informal address.
Lastly, sometimes people do ask me for a license key in a formal, polite way, but sign as "B. Smith". In that case, they either don't really care how I address them, or they don't want me to figure out their gender or full name for some reason, which I must respect. Not one of these people has ever objected to my use of "hi".
Some sensitivity to age and formality is needed to answer this question. A formal note does not change in structure because it's being sent via email. There's nothing special or magical about email that gives one permission to be forward, rude, or insulting.
When writing to older persons, persons in authority, superiors, et al, I recommend a salutation and a complimentary close. These are not "wastes of time" by any means - they serve very specific functions if you are skilled in their use. Both the opening and the close allow you to frame your relationship with the recipient. For example:
Melissa:
Hi Melissa:
Dear Melissa:
These all have a different feel and express a different kind of tone. Paired with the proper close, you have no need for silly emoticons and winkies and such.
However, younger people will find these things to be quite strange and confusing. In sending email to anyone 25 and younger, I'd recommend being extremely curt and you might even be pushing the envelope by using punctuation.
Best Answer
Many variations are possible, and some more common in social than business contexts.
For example, a wedding invitation could be addressed to "The Doctors Doe" or "Drs. John and Jane Doe".