This is my understanding of your question:

• you want to evolve "permutation" objects
• you apparently represent a permutation as a list
• a crossover (recombination) of 2 permutation lists is not guaranteed to remain a permutation list.

OK, so let's think of a different kind of combination operation, one which preserves the permutation nature. How about:

Composition. Given permutations α and β, their composition αβ is also a permutation.

• Possible pitfalls: it's likely that the resulting permutation won't share high-fitness features of its parents, depending on your fitness measure.

Conjugate: Given permutations α and β, combine them as β α β^-1, also a permutation.

• Possible pitfalls: resulting permutation is in the same conjugacy class as α, and therefore has the same cycle structure. The features of β don't have much effect on the result of this operation. Because this operation has some asymmetry, maybe flip a coin to see which parent will get to be the "dominant" parent.

Ok, so I can only think of 2. Maybe try out both? I bet the second one would be nice if your fitness function rewards permutations that have cycles of the appropriate sizes.

If you really insist that your combination operation should be a list crossover, then you can certainly fix it to always produce a permutation. Who says that the crossover operation should be deterministic? After combining the two lists, find all the duplicates. Delete all but one of each duplicated item (you can chose which positions to remove randomly if you like), and fill in all the remaining empty spots with a random permutation of the items that are missing. This seems like a reasonable way to keep a lot of the features of the parents, keep the spirit of the list-crossover operation, and preserve permutation-ness.