There are many very fast and efficient in practice branch and bound 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.