/ bump after 8 years

Check that, for $p=2$, we have $m=n=1$. Also, if $m=1$, then, $n^2+1\mid n^3-3\implies n^2+1 \mid n+3\implies n^2\leq n+2$. In particular, $n\leq 2$ is obtained, and thus, $p=5$, $(m,n)=(1,2)$. Now, suppose that both $m,n>1$, and $p>2$. Observe that, $(m+n)^2\equiv 2mn\pmod{p}$. Furthermore, $m^3+n^3 =(m+n)(m^2-mn+n^2)$, and thus, $m^3+n^3\equiv -mn(m+n)\pmod{p}$. Therefore, the given divisibility reads as, $$ p\mid m^3+n^3-4 \implies p\mid mn(m+n)+4 \implies mn(m+n)\equiv -4\pmod{p} \implies (m+n)^3\equiv -8\pmod{p}, $$using $mn\equiv \frac{(m+n)^2}{2}\pmod{p}$. Now, with this, we have $p\mid (m+n+2)(m^2+2mn+n^2-2m-2n+4)$. There are now two cases to finish the problem: 1) If $p\mid m+n+2$, then $2(m+n)\leq m^2+n^2 \leq m+n+2\implies m+n\leq 1$, a contradiction (we've used the fact that $m,n>1$). 2) If $p\mid m^2+2mn+n^2-2m-2n+4$, then, $p\mid 2mn-2m-2n+4$. Noting that $2mn-2m-2n+4=mn+(m-2)(n-2)>0$, we have, $m^2+n^2=p\leq 2mn-2m-2n+4$, giving that, $2mn\leq m^2+n^2\leq 2mn-2m-2n+4\implies m+n\leq 2$, again, a contradiction. Hence, the only answer is $p=2$ (with $(1,1)$), and $p=5$ (with $(1,2)$).