I hope I'm not completely out of scope going anecdotal here, for the episode in question had a highly educative content at least for me:
Recently I have witnessed a colleague from our ILL team trace down an elusive copy of a scientific Russian magazine. When the first request of a patron could not be fulfilled, the patron replied with a photo of the front page of the magazine in question - he had it in his hands some time ago and was by now desperately searching for an article he remembered reading to reference it.
With the help of another colleague it was determined that the title was of Ukrainian origin, and several attempts were made to transcribe the title from its original Cyrillic script. Eventually one of those transcriptions took hold on one of the search engines fed, and further refinements on the title could be made which made it possible to trace down that the magazine, while in Ukrainian, was actually printed and published in Toronto.
From there it was routine work to find three copies existing within Europe, and initiate an ILL loan on one of them.
The key to searching in this case was the variety on transcriptions/romanizations of the Cyrillic title. Even with two Russian-speaking librarians cooperating on the challenge, it took several attempts to find the title hidden in the latin-scripted databases and weed out all the false positives.
So, apart from the excellent tips math_librarian already mentioned in his answer, I'd add that you might ask a native experienced with transcriptions (and their possible variations) to aid in finding references to the original that could in turn lead you to a possible translation.