While genetic algorithms are useful for solving certain problems, Sudoku puzzles exhibit a strong combinatorial structure that can be exploited by other approaches (Constraint Programming above all, I think).
When modeled as feasibility problems, for instance, their solution can be found very quickly -- it took 0.2 seconds to solve that instance on my laptop.
Constraint programming is definitly the technology of choice for solving Sudoku puzzles. There is a nice article by Helmut Simonis (http://www.4c.ucc.ie/~hsimonis/shikaku.pdf) that shows how good various propagation strengths and model variants are for solving 9 times 9 Sudokus (short answer, full propagation on individual rows/columns/squares plus shaving never needs search).
For 25 times 25 Sudokus on the other hand, propagation alone is in my experience not enough, and a lot of search is needed.
Genetic algorithms usually do exploit the structure of the problem in order to make crossover/mutation more efficient. This is indeed what the OP says:
For more difficult Sudoku puzzles, I would definitely go with the permutation genome
When modeled as feasibility problems, for instance, their solution can be found very quickly -- it took 0.2 seconds to solve that instance on my laptop.