One reason Starfleet may have given Kirk a commendation for original thinking is that the solution he came up with did several things that represent Starfleet values.
1. He chose to try to rescue the ship, showing compassion and concern for others.
2. He doesn't try to outshoot the Klingons. Starfleet needs capable military commanders, but part of that is to try and prevent war.
3. By asking the Klingons to assist him, he shows an understanding of the Klingons sense of honor and duty, while also demonstrating humility in asking for help (though not too much humility, as he did have them recognize him as a famous and renowned captain).
In short, he chose a peaceful solution that saved lives on all sides and avoided a war, the very qualities that Starfleet desires and which would make him an exemplary captain.
The Kobayashi Maru and its Perfect Play A.I. could explain why Kirk is so skilled, and eager, at dropping Logic Bombs on rogue computers. Having tried to outsmart an AI that was programmed to win at any cost, and then figuring a way around the simulation using lateral thinking, Kirk became proficient at outmaneuvering computer logic and probably developed an unconscious hatred for computers in the first place. It could also explain his irritation at the computer with the female personality in "Tomorrow Is Yesterday". As he sees it, it's only a pale imitation of the real thing.
