Guy Steele gave a talk at the MIT AI Lab a few years ago about solving a board game called Teeko. The problem was posed in 1972 but it didn't become feasible to solve (via brute force) until 1998. Unfortunately the talk doesn't seem to be online anywhere, but I remember it having a joke about using Moore's Law to solve an exponential problem in polynomial time.

Also, hi! I only just now figured out who you (and other JBPers with non-obvious LiveJournal userids) are. You were right about the stomach flu warning, by the way. :(