I think that a party search feature would do better once there are more defined jobs. The class system doesn't allow for an easy idea on what kind of player you're going to get, as most classes can tank, can DPS, can heal, etc. It would be nice, however, to at least allow for a search of players currently wanting to party, detailed by rank.
But once the new job system is up, we should have a better idea of what the party search feature should be.