I read your explanations several times and I must admit I don't get all of it, but I think I'm slowly getting there... what about this:

Created 3 categories: Gender, Type and Size.

Category Settings:

Types: All my product classes
Hierarchy: Multiple
Related terms: No tick
Free tagging: No tick
Multiple select: Tick
Required: Tick

Terms:

Under Gender two terms: boys and girls
Under Type several terms: pants, shirts, skirts, etc
Under Size several terms: small, medium, large, etc

Then, as Jorditr said, I have to find a way to present taxonomy/term/number-for-boys etc, right? I always thought the catalog only showed the terms under catalog, but I guess I was wrong. Also I tried to understand what oslinux said about creating the term pants twice, but I didn't quite get that yet...

Hope you don't think I'm thick, I really wish to understand this subject once and for all