That points to the core of the issue. "Fairness" in ML algorithms can be hard to define and assess.
It's easy to say "omit gender from the model", but the real issue here has to do with the _causal_ pathways between your input variables and the output variable.
Since ML mostly works by exploiting correlations between the input and output variables, omitting gender doesn't mean gender's influence is removed. You'll have to omit all the causal pathways from gender -> the output, effectively "d-separating" [1] gender from the output. Whether that's practical or not depends on how well we understand the data generating process.
[1] http://bayes.cs.ucla.edu/BOOK-2K/d-sep.html
