I think that the reason it works for AI War and not some other games is a subtle bit of perception on the part of players. With AI War, we have a core of stuff that is ALWAYS there for all games, for all players. That creates a sense of consistency and predictability.
But, then there's this huge amount of other stuff that is rarely there, except some of it is there randomly in every game. This to players feels like a bonus, rather than like something is being taken away. And, truthfully, if the players had all ships in every game, it would be overwhelming to the point of paralysis.
With the mechanic of randomly taking something away from players, you meet resistance immediately. "Why do you take away something I want!?" etc. There has to be a certain core feature set identified, and then other stuff which is treated as a bonus. If players think of that extra stuff as being core, then you've already lost them I think.
That said, I think board games are a little bit different. In terms of die rolls or cards, it's a bit of a hard sell. But with something like Carcasonne, that gets really well recieved because you get random options but have many ways to skillfully apply it. With a game like DungeonQuest, so much is random and so many of the random things are penalties, that there's clearly very little skill involved in that game. It's more about the experience and shared misery and humor, at least based on my play sessions with it.
I think the answer is always different for every game, but overall players are looking for random options that increase variety between playthroughs -- not which stand in place of strategic choices. That's why there's no random component to the actual combat of AI War, for instance.