I think something that would allow us to definitely solve this problem is profile pictures (which don't have to be your actual picture) or user profiles.

User profiles good, pictures bad.

Frankly, the "problem" here really isn't very hard to solve: just don't assume you know a person's sex unless you actually know it!