Bill Gasarsh posted a list of the surpursing results in the theory:
http://weblog.fortnow.com/2005/12/surprising-results.html

Which are my 10 favorite ones?

1. Matrix Multiplication in O(n^2.87) time (less than n³ !!) (Strassen 1969).
2. Equivalence problem for Regular Expressions with Squaring is EXP-SPACE complete (Meyer, Stockmeyer FOCS72). A `natural' problem proven to NOT be in P!
3. P vs NP cannot be solved by techniques that relatives (Baker, Gill, Solovay 1975).
   
4. Permanent is #P comple
5. Shortest Path problem on planar graphs BETTER THAN O(n log n) (Fredersickson, 1983, FOCS).te. (Valiant 1979)
6. Bit commitment⇒SAT in Zero Knowledge (Brassard,Crepeau FOCS86, Goldreich,Micali,Wigderson CRYPTO86, JACM91)
   
7. Fixed Parameter Tractability material
8. PH in P^#P. (Toda FOCS89, SICOMP91)
9. Connection between PCP and Approximation
10. Grover's Quantum O(n^0.5) search algorithm (STOC 1996, Phy Review Letters 1997