The total re-order of your deck allows for weird best/worst case luck (who is doing the ordering), which is usually really off from the average case. Which mostly makes it into an entirely different game, but one which among other things has ENORMOUS AP - if you get rid of the randomness of the shuffling, the game should be quite directly 'solvable' by pretty direct backward induction, but this will take FOREVER. Of course, you can do this with the probabilistic game we actually have too, in terms of probabilities, but it's so complicated that, like chess, you just aren't going to even try to calculate the game to the end from the start position.
So "Play more games" or "Play a different game" are sort of tongue in cheek, but I think at some point, you do actually have to acknowledge that the luck thing is an inevitable issue with dominion. I mean, we can say the same thing about poker, no? But even something as modest (and complicated) as rod_ suggests in reply#12, you actually get some issues - what happens is that the cards that miss the shuffle all get clumped at the start not only of the shuffle immediately after they miss, but also in the next shuffle. Which lets me plan ahead somewhat for certain collisions. Is it tricky and sorta small? Yes, but especially with software aid, it's doable. And this doesn't solve things like sea hagging a sea hag. The problem is that any way of forcing some regularity in is going to fundamentally change the nature of the game by changing either the percentage of times that particular sets of cards collide downwards or upwards, and you're looking at a quite different game.