I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.
The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; notable among them are connect four and nine men's morris. Additionally, several chess endgames have been solved.
This perhaps doesn't seem like an answer to your question, but if an expert (such as Marion Tinsley) loses to a computer program, then the computer must have found a "more optimal" move.
See Wolfe and Berlekamp -- Mathematical Go. Using Conway's theory of games, they show how to analyze certain kinds of Go endgames. Their solutions turn out to be measurably better than the solutions given by top Go players. (Not quite an answer to your problem, as those latter solutions were probably never claimed to be optimal.)
Chess endgame techniques have been greatly enhanced by the advent of endgame tablebases. Endgame tablebases are lookup tables that solve chess when there are no more than (currently) seven pieces on the board. Here is an online tablebase I've used in the past that works for up to six pieces.
Algorithmically, these tablebases are not very interesting; they are generated mostly by brute force. However, they have contributed to several aspects of endgame theory. Wikipedia has a nice summary of some interesting points here.
These discoveries also had implications for the "fifty move rule," which states that after fifty moves without a capture or pawn advance, either player can claim a draw. Even before computer analysis, several endgames were thought to take more than fifty moves, and the rule was slightly extended in those circumstances (probably the most famous is the rook and bishop vs rook endgame). As the number of positions requiring these moves became larger, these extensions were dropped and the normal 50-move rule was reinstated in all cases. Modern analysis has shown that some endgames take several hundred moves .
This is another interesting article, summarizing some effects of seven-piece tablebases on endgame theory. I particularly like the mutual zugzwang shown in the last position.
It is not properly a "game strategy", however in 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge found that all Rubik's cube positions can be solved with a maximum of 20 face turns using a computer-assisted proof  ... a nice result.
The annotated source code is available at http://cube20.org/src/.
The average number of moves taken by standard solving methods is ~50-60, but there is also an official "fewest moves" hall of fame:
#player #moves 1 Tomoaki Okayama 20 Japan Czech Open 2012 2 Moritz Karl 21 Germany BW Open 2013 3 István Kocza 22 Hungary Czech Open 2010 Jimmy Coll 22 Belgium Barcelona Open 2009 5 Adrian Lehmann 23 Germany German Open 2013
(note that the upper bound of 20 was reached only one time in 2012 ... so in Rubik's cube championships humans are far from playing the "optimal strategy" :)