The solution is absolutely disallow offending titles. The same principle that would make HN moderators take down a "Kill all the Jews" title from the front page should apply for this one too.
Submission titles should be the original article titles, as long as those aren't problematic.
Its not as offensive.
I agree this is problematic, but I am inclined to see it as an opportunity to discuss the problem and illustrate how widespread it is. We can also mention real issues, such as about half of all domestic abuse victims in the UK are male (if you count emotional abuse, otherwise its still 40%), more than half of rapes in the US are of men (because of the huge number of prison rapes), etc.