From a statistical standpoint, at some point you are going to have to consider that you the player has improved and that some deck improvements are really player improvements.
-I personally prefer the 40 card version. I found the 36 card version too variable. I spent some time thinking about the win condition - that is, at what point have you secured a win? I used to think it was getting the walls up. Now I believe it to be once you have the card draw engine going. In essence, the entire deck is 1 giant combo. You need the vast majority of the deck at your disposal in order to win. The way this is accomplished is by getting out the hourglasses. A second or third turn Hourglass is a strong predictor of you winning that game. Once you have 2 hourglasses in play, unless the FG has zerged you bad, you will probably win. It only takes 2-3 turns of drawing 3 cards per turn that the deck just comes together. So that being said, the 40 card version with 4 hour glasses has a higher chance of drawing an early hour glass and also a higher chance of getting 2 hourglasses out.
This observation is likely why so many people were having bad luck with the 36 card version. The deck is very feast or famine. If you get an early hourglass with the 36 version you are golden, but the chances of you getting that early hourglass are lower.