These are my experiences about learning from games.

Good educational games

• Piano game - you had this bird or whatever who first played a melody, and then you were supposed to repeat it. Fun not only for memory but also because you actually memorized how to play a tune. Error/failure was handled by the bird saying "oh no, try again". Clicking with the mouse was hard, but it would probably work better on a touch-screen.You did not have to do as the bird said, you could just play your own thing too. I usually started practicing the birds melodies and then made my own thing out of them. The bird did not protest that.
• Age of Kings and other historical strategy games - they try to work with historical facts while twisting them a little. I especially like these "impossible to win" type of games.
• Sim city - the newer versions are way too complex but SimCity 2000 was pretty ok. You could get into it pretty quickly and get an idea of the problems that a city manager had do solve: sanitation, security, education, business opportunities, dept, distaster management etc.
• Assassins Creed - great exploration of architecture since you can run around on/in the buildings. I'm too poor to travel to these places myself so I had a really great time. I think Ubisoft should release a "non-combat" educational version of these games. Would be awsome! The student could run to some place and make sketches of details of the buildings on physical paper and then do a presentation about it.
• Sandbox puzzle building games - you have a ball which should be put into a basket and some obstacles. Then you shuold use a stockpile of various mechanical things to make it happen. I enjoyed these games when I was 8 and I enjoy these games when I'm 28
• Hypercard DIY games - my first experience (about 7 years old) in game-making. I put together a stack of pictures i painted and clickable areas which represented if-then branching.
• Driving simulators - I'm not talking about grand tourismo games here. Car drives in normal or dense traffic and then the student (me) has to answer questions about how to behave. Great since you can switch perspectives between different cars and see why they cant see you. Thus you will learn WHY it is so important to behave in a certain way.

Bad educational games

• Memory - so boring. I guess it trains memory but it's so brain dead. I think the piano game above was much nicer since you "create something".
• Snoopy math game - the child would type in a answer to a math problem and when answering the correct number there would be cheers like "good job (hands clapping)" and when failing there would be "aww, try again". This destroyes the inner motivation of the child in learning. When sitting in front of a math test or book there will be noone telling you to try again.
• Word and spelling games - just typing in words in a foreign language and you get a yes/no answer. Perhaps these types of games are good if you have problems with spelling, but they are so uninspirational. Typing becomes associated with boredom and agony.

Conclusion

• Having a historical backdrop can teach you a lot - since you have to know about the technological limitations of that time to solve a problem.
• Sandbox simulators are great educational games - forces child to think and facing "impossible to win" scenarios which are hugely educational.
• A game that tells the child in a emotional way when they have done something right or wrong is bad destroys self motivation.
• Most important: whenever you turn education into a game there is a risk that the student will try to win more then learn and thus tries to game the game (learn AI patterns and cheating).

Aren't good realistic simulation programs in and of themselves a great educational teaching tool? Some examples of what I am talking about are Microsoft Flight Simulator, Rail Works Train Simulator, Universe Sandbox and maybe even Americas Army. I understand that the OP is talking about the genre of educational games, but I believe it is still worth noting that we learn more from games than we think. Before I played Gran Turismo I knew absolutely nothing about cars, but now I know at least some things.