The two "house rules" that isotropic allowed you to implement were:
-force identical starting hands
-veto mode.
(and later point counters, which let's not discuss in this thread since they've been discussed ad nauseum.)
I liked veto mode a lot, and even enjoyed the strategy of the meta-game on veto mode. The unfairness of identical starting hands in Dominion doesn't bug me. Neither did the house rule seem to break the spirit of the game. I mean, there's no way you can force things to be identical in Dominion. When my opponent is 5/2 on a Mountebank board, I think, "OK, I'm probably going to lose... but what can I do now to make that less likely?"
To me the much more frustrating shuffle is the second. If I had to house-rule the second shuffle, I would give players the option, on turn two only, of placing an estate on the bottom of the deck. This is unnatural and inelegant, but I can't think of any other rule that fixes the second-shuffle frustration without breaking the game.