An algorithm with complexity O(n^{999}) is polynomial but but not more useful than an exponential algorithm on any practical problem.

If an NP solver comes out, it may not practical (at first or for any practical purposes).

The polynomial complexity of the "P is in prime" algorithm https://www.cse.iitk.ac.in/users/manindra/algebra/primality_... had first a bad polynomial complexity and was later improved in other papers.