There are two ways to interpret your question.

First -- since you are talking about braids, perhaps you are asking about the conjugacy problem for braids. This is the same as taking a braid closure, *with* an braid axis. In this case the ultra summit set (USS) of a braid $\sigma$ is a complete invariant for conjugacy classes. It is an open question whether or not USS($\sigma$) is polynomial sized (and hence polynomial time computable). There are other approaches to the conjugacy problem in braid groups, but none are know to be polynomial time.

Second -- if you are not including the axis, then, by a result of Alexander, every link can be represented as the closure of a braid. So your question might be: is there a polynomial time solution to the isotopy problem for links? No such algorithm is known. That the isotopy question is even decidable depends on Thurston's geometrization theorem for Haken manifolds; also, a great deal of work prior to Thurston is needed.

Finally -- you ask if there is an invariant that fails with only "negligible probability". This is a good question - I don't know the answer. Just to make things clear. You have the following model of random links: (a) chose a braid index, (b) choose a length, and (c) choose a random braid of that index and length in the standard generators. Now take the closure to get a link. This is a perfectly nice model of random links. I suggest you consider the multi-variable Alexander polynomial. It can be computed in polynomial time, and I believe that it fails with probability tending to zero (for fixed index, and as the length tends to infinity).

EDIT: There is a problem closely related to the conjugacy problem in the braid group; this is the determination of the Nielsen-Thurston type of a braid as either reducible or pseudo-Anosov. This has a polynomial-time solution, due to Matthieu Calvez - see his paper Fast Nielsen-Thurston classification of braids.

FURTHER EDIT: There have also been, very recently, claims concerning the conjugacy problem for pseudo-Anosovs (and the general conjugacy problem) in mapping class groups. Margalit, Strenner, and Yurttas have claimed a polynomial-time algorithm that, given a pseudo-Anosov, computes the veering triangulation for the associated surface bundle. This is a complete conjugacy invariant for such mapping classes. Here are some notes from a talk by Margalit.

Bell and Webb are claiming a polynomial-time solution to the general conjugacy problem, based on techniques from their paper Polynomial-time algorithms for the curve graph and using some new ideas.