Right, I know. I agree it makes no practical difference when you don't know the order of your deck. But, with a pedantic player or tournament, it's either obnoxious ("Ok, shuffling for no reason...") or it starts a fight ("It doesn't matter!" "But the rules say you have to... are you going to forfeit?"). I'm sure we all hate playing with people like that; why even give them the possibility of holding you hostage?
Don't play with people you don't like, seems straightforward? And a good move in general, way more likely to pay off in other situations than in this one. In a tournament, man, you may want to rethink your get-Inn-but-don't-shuffle-cards-in strategy. What are the other $5's? And if you have to pointlessly shuffle, get it done quick, these rounds are timed. In an online tournament, the program will do that pointless shuffling for you instantly, np.
I don't really understand what you mean by "Those things add up". Do you mean they create analysis paralysis and/or make the game less accessible? To me, omitting "may" seems like it narrows the strategic space for rarely any benefit. I would have thought you'd rather err on the side of "you may" to increase the depth unless you have a very specific card balance reason not to (Haggler, Bishop, etc). It also has the benefit that if a player forgets to leverage an ability, they haven't actually broken the rules and, well, sucks for them.
What adds up is complexity.
Every card in Dominion can be made better by making it more complex, provided you ignore complexity when evaluating betterness. But making cards better by adding complexity does not lead to a utopia of all awesome cards, it leads to a dystopia of an unplayably complex game. Complexity matters. Adding "you may" because someone you play with might think, oh you have to shuffle your shuffled deck, man, no question, I was never adding that. The cost is small but nonzero; the benefit might as well be zero. In one of the not-every-game games in which Inn is on the table, during one of the not-so-many turns in which you buy/gain Inn, if it is one of those pretty-rare-don't-you-think situations where you actually don't want to shuffle in any cards even though you did want an Inn, and we have no information about your deck order at this point, and you are playing against stupid unfriendly people, well, watch out. That shuffle, combined with your incredible rage at having to do it, could be what finally pushes you over the edge.
In general the strategic depth of "you may" is only worth it if it's common to pick either option. To give you an example, this was a real decision for Spice Merchant. Do you pick the Woodcutter often enough? Well you do pick it some. But you know, if you were picking it much less often, the card wouldn't give you the option, because options that you don't use just slow turns down and make the game more complex. Spice Merchant fell on the side of "okay let's keep it," but that's how unlikely I am to add "you may" for something that rarely happens - I strongly considered not giving you the Woodcutter on Spice Merchant. "You may" wants to be used where it's really worth something, where both decisions make sense a reasonable amount of the time. Or in special cases where it's the simplest wording (obv. "you may" on Throne Room is simpler than "or reveal a hand with no Actions"). The game does not need to gain tiny amounts of strategy in obscure situations via making all cards more complex.
At the risk of being pedantic myself, isn't this essentially what should have happened with Throne Room? I though I read a post from you saying something like "I should have made it say 'may', but oh well". Forgive me if I'm misrepresenting you.
Throne Room should say "you may" because it doesn't keep you honest, and as noted the other solutions are even wordier. Inn has no such problem; you have to shuffle, the end. The fact that you can save time by not shuffling, when you're already shuffled, that's just common sense, but if people miss that it doesn't matter.