I agree that learning can be fun and that we can embed "gaming elements" into our instructional products to make them more engaging.
You have identified several things that you feel should be incorporated into the game, however an example of what you're suggesting would be very helpful, and perhaps provide some focus on how to apply it to a real learning situation.
How about providing an example that incorporates a simple teaching concept into a game (implementing the suggested elements, of course). I'm not suggesting that you provide us with a game, though that would be interesting, but provide the general design, the interactions, the visual display, the logic flow, and most important -the feedback provided by the game to the learner.
Even better would be to discuss examples from a couple of different learning types (teaching a concept, verbal information, a rule (Gagne), a process, problem solving, etc.)