I can sorta get that it's a hard balance to strike, but 1:1000 really isn't "unicorn" rare.
In a population of 50 million, there are still 50,000 men.
If we go by the statistic of redheads being 6% of humans, you would encounter one man for every 60 redheads you encounter. Unless you're living in the boonies, everyone should still encounter a handful of men in their life.