And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.

Maybe, but that feels significantly more exotic and unlikely to me. You have to basically negate the natural cost scaling of brute force in the thousand to million n range but lose that speed benefit later.