In his article where he stated what we know as Eisenstein's irreducibility criterion (which actually was first proved by Schönemann, as was Scholz's reciprocity law and Hensel's Lemma), he claimed that the result also holds in the following case: assume that $$ f(x) = x^m + a_{m1}x^{m1} + \ldots + a_0, $$ where the $a_i$ are integers divisible by $p$, and where $p^2 \nmid a_j$ for some $0 \le j \le m1$. There is an obvious counterexample provided by the quadratic polynomial $f(x) = (xp)^2 = x^2 2px + p^2$, so that could be the end of that story. But it isn't: I've read somewhere that some form of this criterion holds for polynomials of degree $\ge 3$, and that the degrees of the possible factors of counterexamples can be predicted in terms of this index $j$. Unfortunately, I don't remember the exact statement (those who are familiar with Newton polygons will probably be able to figure out a correct version) or where I've seen this. Can anyone help?

Basically all such criteria boil down to some argument involving the Newton polygon as Kevin Buzzard mentions in the comments. While something as general as your statement has trivial counter examples the following generalization holds:
I've heard this called the EisensteinDumas criterion of irreducibility (it also proves the example given in the comments). Another generalization of Eisenstein's criterion is the following:
(This is how you prove for example, that a polynomial like $x^n+5x^{n1}+3$ is irreducible, after checking that it has no linear factors.) If not answering your question, at least I hope that this refreshes your memory of the statement you claim above. :) 


Such a generalization (Dumas' theorem) was discussed here: Is a polynomial with 1 very large coefficient irreducible? A good source to learn about it is Prasolov's book on polynomials: http://tinyurl.com/prasolov  see page 53, Dumas' theorem (and a bit before this theorem). 


Franz, if memory serves correct there is extensive discussion of variants of Eisenstein's criterion and relations with Newton polygon's etc in some of Filaseta's work, e.g. in his interesting book (draft) "The theory of irreducible polynomials". It was previously available at [1] but you may now need to write him for a password to access it. He also has some software available, e.g. Java applets for computing Newton polygons, etc. [1] http://www.math.sc.edu/~filaseta/gradcourses/Math788F/latexbook/ 


I've meanwhile found something in
MacLane referred, among others, to the article
There, Netto proved the following: A polynomial $$ f(x) = x^n + a_{n1} p x^{n1} + \ldots + a_{k+1} p z^{k+1} + a_k p^2 z^k + \ldots + a_0 p^2 $$ with degree $n > 2k$, in which the $a_j$ are integers such that $p \nmid a_0$, does not have a factor of degree less than $k+1$. This is similar to Gjergji's second example, but allows the divisibility by $p^2$ that I had had in mind. 

