I will try to respond to the abstract question, with a perspective from Germany (that may or may not be valid for other European countries):
Is the master's in X PhD requirement in Europe satisfied by a master's in Applied X rather than Pure X?
The general answer to this is yes.
As opposed to the subject chosen for the Bachelor and Master degree, which is usually supposed to be the same or closely related in Europe, as Bachelor and Master curricula are closely coupled here, a PhD is often completely disconnected from the former studies.
Note that the Austrian website that Moritz linked to in the original version of his answer does not require a particular Master's degree, but a "relevant Master's degree". Without any further restrictions, this means that anything closely related to the subject (and the relationship between Applied X and Pure X might very well be sufficient) should do. At least, that would be the interpretation in Germany; it is possible Austrians interpret this differently.
However, it is also very well possible that the suitability of the Master's major is determined based on the research projects at hand. In that case, it depends entirely on the decision of the respective department chair, and it would be worthwhile to contact departments you are interested in. As a concrete example, it is completely normal in Germany to see Masters of Physics, Linguistics, and Maths starting PhDs in Computer Science, not only Masters in Computer Science.
EDIT: To clarify the last remark: None of them have to take any extra courses; rather, they are expected to bring their professional subject-specific knowledge from physics, linguistics, and maths, respectively, into their computer science research (while "informally" (i.e. without a class) catching up with the CS knowledge), just like Masters in CS are expected to use their professional CS-specific knowledge in their computer science research, while "informally" acquiring knowledge on (w.l.o.g.) physics, linguistics, and maths, as required for their respective research.