At first, or can the cards be shuffled so that one could never win no matter what they did?
And is it possible to mess up so badly one cannot win?
Which type of solitaire?
It is my understanding that in virtually all types of solitaire played regularly, some hands cannot be won, and that many winnable hands are lost because they are not played properly. I have no cite for this, but recall reading it in a games theory article once.
Regular solitaire (like the Windows Solitaire) can be unwinable. I have had all red cards to build off of and only red cards coming up on the deal (both with real cards and on the computer).
Freecell has at least one non-winnable game, but something like 99.99% of the games are winnable.
I imagine it wouldn’t be hard at all to construct a game of Klondike that’s not winnable. You have seven cards showing on the stacks, plus 24 in the draw deck, of which you can see eight if you don’t play any. So that’s 7 + 8 = 15 available. Just make sure that all 15 of these cards are non-Ace black cards, and you won’t have any legal moves, ever. Since there are 24 non-Ace blacks, it’s pretty easy. This will happen about once every 3.4 million games. Since the same is true of reds, at least one in 1.7 million games of Klondike is non-winnable. It’s even happened to Swede Hollow, apparently.
Regular old solitaire has many unwinnable deals, I’ve read. Also. 
I’m assuming you mean “regular” solitaire like the one that comes with Windows… consider this layout:
The cards on top of each pile are the 2, 4, 6, 8, 10, and Q of clubs and 2 of spades. Then there are 1+2+3+4+5+6 = 21 cards underneath those in the piles. Put all the odd red cards, of which there are 14, down there, plus the two black aces, plus anything else. Then all that’s left for you to draw from are even red cards and assorted black cards, and no aces, so you can’t make a move at all… at least I think.
Upon preview: Freecell does indeed have at least two non-winnable games; try selecting game # -1 or -2.
Hehehe, thanks for the info, Desmostylus. I actually played the first 2k or so games of Windows Freecell to try to find an unwinnable game (without doing any checking to see if anyone had already found any). Well, that and I am an enormous geek. I still have the piece of paper around here somewhere where I’d write down the game number I ended on.
Hey, it got boring at Michigan Tech sometimes. When my friends and I were sitting around drinking and talking, I’d be cycling through Freecell games.
Did I mention that I’m an enormous geek? And I don’t mean that I’m fat, either…