"Has there been further progress in this area since 1993?"
So far as I know, there has been no direct progress. I feel semi-confident that I would know if there had been a big breakthrough: Mazur was my adviser, this is one of my favorite papers of his, and I still work in this field. Also, I just checked MathReviews and none of the citations to this paper makes a big advance on the problem, although two are somewhat relevant:
MR1905389 Thăńg, Nguyêñ Quoc On isomorphism classes of Zariski dense subgroups of semisimple algebraic groups with isomorphic $p$-adic closures. Proc. Japan Acad. Ser. A Math. Sci. 78 (2002), no. 5, 60--62.
MR2376817 (2009f:14040) Borovoi, M.; Colliot-Thélène, J.-L.; Skorobogatov, A. N. The elementary obstruction and homogeneous spaces. Duke Math. J. 141 (2008), no. 2, 321--364.
I'm not sure what you mean by an effective bound on Shafarevich-Tate groups (henceforth "Sha"). It is certainly expected that the Sha of any abelian variety over a global field is finite. If this is true, then in any given case one can, "in principle", give an explicit upper bound on Sha by the method of n-descents for increasingly large n. (In practice, even for elliptic curves reasonable algorithms have been implemented only for small values of n.) I really can't imagine any algorithm having to do with Sha that has "a priori bounded running time". What do you have in mind here?
As to the final question, let me start by saying that it seems reasonable at least that the set of "companion varieties" (i.e., Q-isomorphism classes of varieties everywhere locally isomorphic to the given variety) of a projective variety V/Q is finite: as above, we believe this for abelian varieties, and Barry Mazur proved in this paper a lot of results in the direction that the conjecture for abelian varieties implies it for arbitrary varieties. (For instance, quoting from memory, I believe he proved the implication for all varieties of general type.)
Here is a key point: suppose you are given a variety V/Q and you are wondering whether it has rational points. If V is itself a torsor under an abelian variety (e.g. a genus one curve), then if you can compute Sha of the Albanese abelian variety of V, you can use this to determine whether or not V has a Q-rational point. In general, the connection between computation of sets of companion varieties of V and deciding whether V has a Q-rational point is less straightforward. If V is a curve, then there are theorem in the direction of the fact that finiteness of Sha(Jac(V)) implies that the Brauer-Manin obstruction is the only one to the existence of rational points on V. In particular, people who believe this (including Bjorn Poonen, I think), believe that there is an algorithm for deciding the existence of rational points on curves. But nowadays we know examples of varieties where the Brauer-Manin obstruction is not sufficient to explain failure of rational points.
So, in summary, it is a perfectly tenable position to believe that companion sets are always finite, even effectively computable, but still there is no algorithm to decide the existence of Q-points on an arbitrary variety.