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".