The answers to the four questions posed are certainly going to vary based on the expert consulted. Phrase structure grammarians view aspects of word order differently from dependency grammarians. I will take each of the questions one at a time:
What are the main differences between Meaning-Text Theory (MTT) and phrase structure grammars.
The answer to this question is straightforward. MTT is a dependency grammar (DG) and proud of it. Igor Melˈčuk, the primary linguist behind MTT, argues vehemently that phrase structure grammar (PSG) is logically nonsensical, involving much redundancy in how it understands syntactic structures. Thus, one needs to understand the difference between dependency and phrase structure in order to begin to understand MTT. The articles in Wikipedia on dependency grammar (https://en.wikipedia.org/wiki/Dependency_grammar) and phrase structure grammar (https://en.wikipedia.org/wiki/Phrase_structure_grammar) can help build this understanding.
It is claimed that MTT is more successful in explaining the free word order in languages like Russian, however, is it equally suitable for any language?
The answer to this question varies based on the linguist consulted. MTT people will answer confidently with Yes! Phrase structure grammarians, in contrast, will be skeptical of this answer.
The reason many DG people view dependency syntax as more appropriate for the syntax of free word order languages is that DG structures are relatively flat compared to those of PSG. These flatter structures allow fewer discontinuities (i.e. fewer crossing lines) in the tree analyses. The layered analyses of PSGs, in contrast, lead to many more discontinuities, which means PSGs are more likely to reach to some means of rectifying the discontinuities, such as movement (or copy and remerge). An insightful discussion of discontinuities from both perspectives, DG and PSG, can be found in Wikipedia (https://en.wikipedia.org/wiki/Discontinuity_(linguistics).
Does MTT really have advantages for natural language processing?
MTT people would likely again answer this question with a firm Yes!. I think, however, that any advantage MTT has in this area is due to the fact that it is dependency-based rather than phrase-structure-based. In other words, DGs in general have the advantage over PSGs in the area of natural language processing (NLP). Consider in this regard that in the field of NLP, the DG approach to parsing is dominant, so much so that it is the standard by now. The simplicity of dependency syntax makes it easier to use and hence more appropriate for the practical goals associated with NLP.
How big is the divergence between MTT and other dependency grammar approaches, such as Tesnière's framework?
The divergence is large. The most distinctive trait of MTT is its multi-stratal nature. There are 7 strata: one semantic stratum, 2 syntactic strata, 2 morphological strata, and 2 phonological strata. These strata are organized hierarchically, the semantic stratum being the deepest and the surface phonological stratum being on the surface. A mapping procedure relates each stratum to the next higher stratum in the hierarchy. The system is incredibly complex in this regard.
Most other DGs are much less complex. Some of them are monostratal (just one stratum), such as Word Grammar and the particular DG I prefer. Others may posit just two or three strata. Concerning Tesnière's syntax, I think it is fair to say that he posited two strata, a deep stratum (associated more with the speaker) and a surface stratum (associated more with the listener). Tesnière was not so explicit in this area, however.
A crucial aspect of Tesnière's syntax is that it is in fact a hybrid system, that is, it combines both dependency and phrase structure. The second half of Tesnière's volume The Elements of Structural Syntax (1959) presents the subtheory of Transfer, and Transfer is in my view quite clearly a manifestation of phrase structure, not of dependency structure.
One final comment. My particular exposure to MTT goes only so far. However, what I found most insightful is Melˈčuk's distinction between semantic, morphological, and syntactic dependencies. The Wikipedia article on DG discusses this distinction a bit ((https://en.wikipedia.org/wiki/Dependency_grammar), it does so in the subsection on types of dependencies (Section 5).