The explanation for the poor result from your Minimize run is that when Minimize is given
approximate numbers (floating-point), it switches to NMinimize which handles floating-point
numbers better. NMinimize is less clever about dealing with local minima. When Minimize
is given an equation and constraints that use only exact (Integer or Rational) numbers,
it can use more mathematical techniques.
In[1]:= Minimize[{9.0 n (m - 1.0)^4 + (m n - 2.0)^2, -1.0 <= m <= 4.0 && -1.0 <= n <= 4.0}, {m, n}]
Out[1]= {-143., {m -> -1., n -> -1.}}
In[2]:= Minimize[{9 n (m - 1)^4 + (m n - 2)^2, -1 <= m <= 4 && -1 <= n <= 4}, {m, n}, Integers]
Out[2]= {-693, {m -> 4, n -> -1}}