Because of this I never had any context for the gender. I assumed their first name was a male name. Now, however, after realizing my mistake I googled and it's commonly a female name.
I done this once in the past but the reverse. A male with a female name. Never corrected me and I didn't realized until we met in person. I also seen signatures where people would put "Mr" in front of their name just as a hint that they are a male rather than incorrectly referred to as a female.
I think the best way to handle this in the future is to simply use the person's name, rather than trying to say "him" or "her." I also suspect that since they didn't correct you or seemed shocked by it, it's probably not the first time it happened.
Best way to handle it in the future is to use their name rather than attempt to figure out their gender. For example, if the person's name is Dana, simply say, "Dana, the files are missing. Can you check from your side? Thanks." Instead of using Sir or Ma'am, or Mr or Ms.
Once you know for sure who it is, I would still use their name as oppose to pronouns. As far as this issue, I would just continue on. You can make a short sentence:
"Dana, thank you so much for meeting me. I apologize for previously referring you to as Mr Dana. Thank you."
Just do it like that and you're set. There's nothing bad about your statement and nothing wrong with anything else. As I said if you just refer to them by their name. Replace Him or Her with their name. For example, if Ralph needed to contact Dana, simply say:
"Ralph, Can you find out what happened to the missing files? Dana is stating the files were sent. Thanks."
"Ralph, get with Dana. He says the files were sent." which may not be correct since you never met or spoken with the person before.
Simple changes and no issues at all.