I've kept careful track of all of my games vs. Fire Queen, and I can verify that the cards in her deck change between each game. I've decked her with no cards in hand on seven occasions, and she has had 3,5,5,5,6,7, and 8 Feral Bonds in play at the end of each of those games, and I don't Steal or destroy them ever. I feel fairly confident in saying that there is a percentage chance of each card in their set being drawn on each occasion, so you can't ever count cards against the False Gods.
I imagine the same is also true against the other AIs.