Thanks guys, a combo of both your answers got me to the solution, which uses directed queries and the idea of root skills, which seem to perform all around better.
The query now looks like:
MATCH (p:Person {id: 100}) - [h:HAS_SKILL] -> (s:Skill) - [r:IS_IN_CAT*..] -> (parent:Skill) <- [r:IS_IN_CAT*..] - (s2:Skill) <- [h2:HAS_SKILL] - (p2:Person)
The introduction of the parent made the difference since it allows the queries to remain directed.
The queries are now generally sub-second for very large graphs 