I could see the translator fairly quickly coming up with a translation for a language that is related, heavily influenced by, or descended from known languages. Like, I could see a Star Trek grade AI eventually figuring out Japanese if it already knew Chinese and English, because you would have enough touch points through borrowed words to work out syntax and such, e.g., subjects usually go HERE in the sentence, this syntax is only used by adults talking to children, etc. I could also see it working if the aliens provide a first contact package of some kind -- like, number sequences, samples of speaking etc. A very, very basic form of that would be what humans sent out as part of the Voyager probes.
A program would have to have SOME clues, though. The reason the Rosetta stone was so important to deciphering hieroglyphics, if I recall correctly, was that it showed the same text in two other known languages. That was the start of a key that let archaeologists start piecing together the meaning of the rest of it. There are examples of what we think are writing from ancient civilizations that are indecipherable. We have no idea what they say, because they were found isolated without context, and weren't based on any known system of writing.
So, in my writing, the translator is good but not magically capable of understanding everybody...and I'm going to say that our "historical documents" of the Star Trek universe are simplifying things for television.