Multiple questions, so multiple answers :)
Tabu Search gets out of local optima, here is an image showing how. It accept worse solutions if all improving solutions are tabu (and not aspired) and either all moves have been evaluated or a selectionLimit or acceptedLimit has been reached.
Both TS and SA can be written "reproducible", which means that running it twice will produce the same results. I presume that's what wanted to imply by saying "completely deterministic" (which is a different property). The trick to get reproducible is simple: just reuse the same Random instance everywhere and initiate it with a fixed randomSeed.
TS, when scaling out, will be unable to evaluate all possible moves per step on a reasonable sized dataset. So it needs to resort to random selection too.
TS, SA (and Late Acceptance for that matter) are competitive. It depends on the use case which performs best (which is mostly impossible to predict in advance). So the required constraints can impact which performs best, but the actual dataset has far less impact.
Note: I am affiliated with OptaPlanner (java, open source).