So, actually I'm struggling with how to answer this question so that it satisfies you as well as every other person who might have a similar problem as you encounter now. I could think of several ways how to encounter this situation, so if my answer doesn't hit your context please provide your context in comment and I'll extend my answer.
However, first of all, you have to pay attention on addressing your contact in a proper way, i.e. if you're per Du or per Sie. That means, if it is OK to address your contact with his first name you don't need Sehr geehrte(r) and you can just stick with Hallo. But you will usually not combine Sehr geehrte(r) with the first name. So you'd go with either of the following salutations:
Sehr geehrte Frau Mustermann
Sehr geehrter Herr Mustermann
Hi (or Hallo) Erika
Said that, I'd like to elaborate on the problem don't knowing the person's gender.
The German language itself doesn't offer a lot of possibilities. And those I can think of do sound quite awkward in your context. Namely I'm talking about Sehr geehrte Damen und Herren. This is a salutation commonly used in job applications when you don't know who'll read your application. But since you already have a contact in your given context, it would be sound very strange for your contact addressing him/her with this salutation.
Besides that, there's another reason why I really recommend to figure out what the person's gender is. Imagine you would always avoid addressing the person in a proper way just because you don't know their gender. On the one hand the person might feel uncomfortable if he/she recognizes your uncommon addressing and/or it could be very embarrassing to you if he/she finds out after months of conversation.
There are a lot of ways to find out one's name. One of them, already provided by another answer, is to use the Internet, though I see this as the last instance to go through.
Alternatives are based on your relationship to your contact. Let's say he/she is a customer, then you can (1) ask your fellows if one of them had already contact with him/her or (2) call the company and ask them [*], or (3) if you have a direct phone number call the person themselves and you'll likely hear their gender from his/her voice. Then of course you should be prepared with an excuse why to phone them, e.g.,
Guten Tag Herr Mustermann (or Frau Musterdame), bezüglich ihrer E-Mail-Anfrage möchte ich Ihnen kurz eine Frage stellen, um gezielter auf ihr Anliegen einzugehen...
(In English: regarding your e-mail I've a follow-up question to narrow down your request.)
If you really see no way of how to ascertain the name of your contact then stand by your problem and say it appropriately in your response. Appropriately here means to keep the formality and sensitiveness for such an inconvenient question. How to? That's up to you, here a suggestion
Vielen Dank für ihr Schreiben vom 27 August. Zuerst möchte ich mich dafür entschuldigen, dass es mir nicht möglich war, ausfindig zu machen, wie ich sie angemessen anspreche.
(In English: Thanks for your letter. First I'd like to mention that I'm very sorry for not being able figuring out the appropriate way how to address you.)
If you're feeling uncomfortable with such a way then, and only then, use the Internet to find out the most likely gender. If then you're barking up the wrong tree your contact will correct you in their response.
[*] That's also suggested in case of job application to ask first who'll be the contact for hiring.