I play a lot of Solitaire games on my Android phone and love to keep an eye out for the statistics.
Given that the Solitaire version lets you restart the game endlessly, I usually play until I solve it. But I never managed to solve more than 80% of the games played (1000+).
So now I wonder, is every Solitaire game solvable?
No. Example: If all of your cards face up on the board are red, and the cards that come up every third card are also red, and none of them are aces. You lose. Do not pass go, do not collect $200.
There is very interesting reading at wikipedia about this topic.
For a "standard" game of Klondike (of the form: Draw 3, Re-Deal Infinite, Win 52) the number of solvable games (assuming all cards are known) is between 82-91.5%.
Literally just played a game in which one of the stacks (the one containing 4 cards) was lead by the 9 of diamonds, and the cards inside of it were the King of Spades, the 5 of diamonds, the 10 of spades, and the 10 of clubs (I know this because I had the entire field solved except for this stack and used process of elimination). As far as I can see this makes the game impossible. I have a 9 of diamonds in which can never be moved, as the two 10s that it's eligible to rest upon are trapped underneath it in the stack face down. Attempting to get rid of the 9 by moving it to the diamond stack would also be fruitless, as the 5 of diamonds is stuck underneath it too. Unless someone can tell me some way that this could be solved, I'm pretty darned certain that if a card that is leading a stack is covering a stack that contains the two cards it is capable of resting on, and a lower number of it's own suit, then the game is made impossible right from the get-go.
Solitaire is a game that precedes its computer version, and that means that all the cards are truly shuffled, without the computer peeking in to verify the game is solvable.
And like McKay mentioned, with a random shuffle you can definitely end up with an unsolvable game.
I'm sure it is possible to design a Solitaire variant in which each game is solvable, though.
No. Eric Sink decided that he would start a micro-ISV to create a version of solitaire that is always winnable. This was mostly just an experiment to see what it would be like running a software company with one person, but he eventually sold the product which is still available for purchase.
There have been some estimates about the number of Klondike Solitaire games that are unplayable (no moves possible, about 1 in 400), and several guesses about how many games are unwinnable, although this percentage varies wildly from 30%-10%.
The difficulty of this problem stems from the sheer number of initial deals 54! that would need to be evaluated to determine which were winnable and which were not.
52! ? (unless you expect the jokers to be dealt, too)
However, if you started a list and enumerated the initial conditions -- I feel like I've seen this on a linux version of Solitare: the numbering of deck order, that is -- and you definitively decide a certain one is un-winnable, you then could compare notes across nodes (share with friends) and VOILA: a list of un-winnable starting deck stacks.
I've been starting to think the Windows 7 version has the un-winnable decks removed, ... I don't know, it's a little heavy-handed and smug about the statistics.
for 1 to 52! getdeck, try solving game, add to statistics at each point only one deck need be stored, and the statistics can be quite small.
I've recently written a paper (accepted to ModRef 2024) on this exact topic. We used a programming technique called constraint progamming to find "blocked" layouts - a provably unsolvable layout requiring a card to move before itself (impossible). This can generate some quite complex layouts which are provably unsolvable: 
In the above, assume that the four kings and two black sixes are available to be played in the stock. The seven piles in the top of the image represent the tableau. Relevant face-down cards have been shown as face-up for clarity (e.g. 7 of hearts).
We estimated the upper bound for the number of games of non-thoughtful (position of the face-down cards is unknown) deal-3 Klondike solitaire to have a 95% confidence interval of 81.942 ± 0.081%. This is the "most popular" variant of Solitaire.
This suggests 18.058 ± 0.081% cannot be solved, regardless of the moves made.
To add to the other great answers, this link has a nice explanation of how a deal is un-winnable. Reasons for Getting Stuck in Klondike Solitaire
The two black 5's are blocking a red 6 and a lower card in their suit. Thus they can not move to a different tableau pile and cannot move to the foundations.
