Were you able to read the German references? If not, just politely explain to the editor that you can't judge the paper because you can't read the papers it references, and leave it to the editor to decide.

@JeffreyBosboom: I happen to be fluent in German, I did read one of the references and I could read the remaining ones once I get hold of them (virtually none of them is available online even if they are fairly recent -- this is also something that is bothering me, maybe I am just paranoid). But I guess one cannot expect that from an average reader...

In chemistry it would be fine to cite German references. I'm completely shocked that anyone would even consider rejecting a paper based on the language of the references.

@DavePhD Maybe German in Chemistry is like French in (pure) maths. But in CS is highly uncommon to have any other language. Especially since, as OP says, none of them was available online, which might be interpreted as suspicious.

OP, you might want to consider anonymizing your user handle. The information you gave about the paper you're reviewing is quite likely enough to reveal its identity to the author and other people who are familiar with it, so you're jeopardizing your anonymity as a reviewer by using your real name.

@DavePhD Again, this is a well known result. The problem of the OP is also that he couldn't even find these obscure results. I have also cited Minkowski's results in German or Euclid's Elements in Greek language for example, but this is easily accessible or well known reference

The author might be making the simple mistake of citing for historicity rather than for readability. This is like citing a paper by Schur in representation theory: yes, that might be the original source, but this is not where a reader would want to look things up. Tell the authors to include references for readers too.

Your job as a reviewer is to check the paper's correctness, relevance, and intelligibility. The language or accessibility of the references should not factor into your recommendation. You must leave this to the editor. If you are unable to properly review the paper because you can't read the references (due to language barrier or because you can't find the references) then you should not review it.

@Szabolcs - If the primary audience of the paper can't understand the paper without resulting to translation, and going on a hunt for references, then isn't it unintelligible to the audience as presented?

I am somewhat dismayed that "Available online" is now a condition for references. Admittedly, my research was in pure math, but I had a taste for somewhat archaic concepts (e.g., cyclotomy) in which deep results dated back to Gauss. Whom I cited in Latin.

A significant proportion of your audience might find the German easier than the English. You're thinking very parochially.

@AndrewLazarus Gauss’s work is available online. In Latin. (I’ve also cited it.)

@JeffE The part I liked best was Latin for "the remainder is left as an exercise". Who could believe that phrase was so old!

Frankly, if a referee used that ridiculous reason to reject a paper of mine and the editors upheld it, I would probably take it as an excellent reason to take that one and all my future publications to other journals that hopefully have a better understanding of how science works. Accessibility to the audience (both in language and in availability online and open-access) is a criterion for choosing between two otherwise-equivalent references, and never a factor on whether a given paper contributes relevant background that needs to be cited.

Just how hard are these to obtain? For example, how many libraries are listed as holding the journal or copies of the papers in WorldCat?

Providing translations of substantial portions of text may well be problematic. First, I don't see why it's the paper authors' responsibility to translate large chunks of the literature; second, a translation is a derivative work under copyright law, so this gets complicated.

@E.P. Referees do not reject papers only provide recommendations. Perhaps I can not strongly recommend your paper for publication because I do not have an adequate background to understand it.

@emory ... which is why my comment is phrased as "used that reason to reject" followed by "and the editors upheld it". An upheld rejection on those lines is even more of a condemnation on the editor than on the reviewer, and that is the reason I would take my publications elsewhere, not some souring over a single rejection.