I believe that type checking in unextended Hindley-Milner type systems is exponential, so, even if the algo is guaranteed to terminate in theory it might not do so before the heat death of the universe. Again, in practice outside of test cases demonstrating this 'feature' it doesn't matter.
Yes it recursively solves for function typing parameters though the call graph. This isn't guaranteed to exit.
If the language you are using annotates function argument's with types[1] then this behavior is avoided and Hindly-Milner becomes effectively linear. This is why type-inference is starting to become a common feature in most languages.
[1] Nearly every language does this, but inline clojure are sometimes type inferred. Depends on language/language family.
This is a similar result. The fact that the Java type system is turing complete doesn't stop us expressing things with it. It just tells us there are some things we can't say about ALL Java type declarations.