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\_{m-1}x^{m-1} + \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 m-1$. There is an obvious counterexample provided by the quadratic polynomial $f(x) = (x-p)^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?



Variants of Eisenstein irreducibility
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:



> 
> Let $R$ be a unique factorization domain and $f(x) =a\_nx^n+\cdots +a\_0\in R[x]$ with $a\_0a\_n\neq 0$. If the Newton polygon of $f$ with
>  respect to some prime $p\in R$ consists of the only line segment from $(0,m)$ to $(n, 0)$
>  and if $gcd(n,m) = 1$ then $f$ is irreducible in $R[X]$.
> 
> 
> 


I've heard this called the Eisenstein-Dumas criterion of irreducibility (it also proves the example given in the comments). Another generalization of Eisenstein's criterion is the following:



> 
> If $p|a\_0,a\_1,\dots,a\_k$ but $p^2\not | a\_0$ then $f(x)$ has an irreducible factor of degree $\geq k+1$
> 
> 
> 


(This is how you prove for example, that a polynomial like $x^n+5x^{n-1}+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. :)


