It's good to have a smart man in the room, but sometimes the smartest man in the world is going to be wrong. Sometimes, research proves faulty or incomplete. With that said, I'm not going to attempt to identify who first used the term Teufelhunden or Devil Dogs, but I will point out that if one mistranslates the English or the English meaning that the German translation will also be wrong.
I came across the story at TAH, but followed the link to the "Rumor Doctor" to find out how he came to the wrong translation. Then I looked for my English-German Dictionary to make sure I wasn't wrong. When I didn't find it, I looked one up online. The online dictionary produced no results for "Teufelhunden," "Devil Dog," "Devil Dogs," etc. It suggested looking up the component words "Devil" or "Dog."
A second online dictionary produced similar results, but also afforded "online translation." It translated "Devil Dogs" as Teufel-Hunde, which demonstrates the challenge of computer based translators as there should be no hyphen. If you instead enter "with Devil Dogs" it translates it as "mit Teufel-Hunden," where the error is simply the hyphen. It translated "Devil's Dog" as "Hund des Teufels" which is the long form of the name the Rumor Doctor gave.
A Devil's dogs would correctly translate as the Rumor Doctor suggests, roughly to Teufelshunde.
But to correctly translate "Devil Dog" to German one must understand German Grammar and the German standard for creating new nouns. "Einhorn" for example is a Unicorn but literally means "one horn."
The Germans hence have the word "Kampfhund" for attack dog (literally "battle dog") "Polizeihund" (police dog) and "Schutzhund" for guard dog (literally "protection dog") which is different from a watch dog "Kettenhund." "Hundeleben" is a "dog's life," of which we all dream.
In this same construction, "Devil Dog" would in fact translate to "Teufelhund" and "Devil Dogs" to "Teufelhunde" or dependent on usage "Teufelhunden." The difference between the two forms of the plural is the difference of a subject or an indirect object in the sentence.1 But getting that declension correct can be troublesome for English speakers. Had a Marine heard someone speak of "mit Teufelhunden," why would he later use "Teufelhunde?" Or if the Germans said "Diesen Teufelshunden haben wir es gezeigt." "Wir heißen ihnen Teufelhunde" (We call them devil dogs") it would explain very well the translation and spelling, while breaking the word up would just make sense (though be wrong) to an American.
The recruiting poster above makes only the mistake of seperating Teufel (devil) and hunden into two words and I guess one could say as well that they got the wrong declension of the word. Now, if we were talking about a dog owned by the Devil, that's a totally different manner, as his friend's Google Search provided.
Of course if you wanted to translate "Devil Dog Recruiting Station" to German, using standard German style of noun creation, it would be: "Teufelhundrekrutierenstation" but I think they may have a different word for "recruiting station," so don't quote me on that, even though it is a valid noun created from the individual German words.
Is all of this a trivial argument? No moreso than the original argument that the Marines got it wrong. By the way, most of the Rumor Doctor's stuff is interesting and as far as I can tell correct. This time, he simply got it wrong, but that is the nuance of language, more difficult when a foreign language.
1. A Grammar of Contemporary German, 1976, Max Hueber Verlag, Munich