One of the reasons I suspect for it having this slightly feminine feel could be because the sentence has been made indirect by the use of の. So when you ask a question that uses の, the の itself is the question which in itself "contains" the more direct sounding words (i.e. the actual question itself).
So walk up to a guy on the street and say:
すみません、郵便局を探しているんですけど
What you're really saying is "excuse me, the reason I'm here, the reason that I stopped you on the street, the reason you're looking at me right now, the reason for our current shared existence is that I'm looking for the post office, and (I want you to help me)"
This reasoning can be applied anytime you see one of these の's.