Quina's gender isn't really a mystery: Quina's androgynous, problem solved.

As for the FFVII mystery... there was a wonderfully long thread on it, but I think it's been dead for a while. Still, it'd be nice if somebody could take a new approach...