There are many very fast and efficient in practice [branch and bound][1] algorithms for different NP-hard problems that we can not rigorously analyze: TSP, Steiner tree, bin packing and so on.

Also there are very nice algorithms for max-flow that are in practice almost linear, but only $\Omega(nm)$ bounds are proven for them.


  [1]: http://en.wikipedia.org/wiki/Branch_and_bound