While I don't know how readily Dominion conforms to the definition of "procedurally generated", it's interesting to consider how its lessons can be applied to creating unique experiences in repeatedly-played video games. The game is always built on the same foundation of rules (expansions notwithstanding) and every game has the same goal. The difference in each game is the selection of actions available to each player, and the thrill is in attempting to compose a more effective sequence of actions than any other player.
To make this interesting, you need both a very wide pool of potential actions, and the mechanics of each action need to be designed such that feedback loops arise naturally.
Dominion gets off easy here, as the "medium" through which different cards interact is the very simple system of resources: actions, gold, and buys. You can create an enormous selection of cards just by having any given card grant some unique combination of these three resources, and then attempt to balance the card by dialing up or down its cost. It's all very abstract, and that eases the burden on the designers.
But how do you do such a thing in a video game, where actions are usually not abstract, but specific (and as a result, limited in number)? What medium of interaction do you exploit to create the game-breaking feedback loops that are the delight of a Dominion player? Better still, how do you make it so that the interactions between actions are subtle enough that game-breaking strategies are non-obvious, making them a joy to discover?
Off the top of my head, you could start with a game that already has a huge number of actions and create a replayable game mode where you limit the number of available actions. Let's use MMOs as a concrete example. You could just take World of Warcraft, assemble four five-man parties, and then present each party with the same randomly-reduced selection of the game's classes, where each class is limited to only one or two of the three talent trees, the class' usable abilities are pared down, and the talents within each talent tree have been shuffled randomly. Each group then races to assemble a functioning party and see who can down the most bosses in a non-randomized dungeon. And instead of instancing each party, you could just pseudo-instance them: for instance, downing a boss makes that boss unavailable to kill for any other group, rewarding groups who made hasty party selections (but punishing them if their hasty selections slowed their ability to deal with the trash mobs leading up to the boss).
I dunno, I suppose it could be fun with enough effort.