Why don't you go into nslookup and type in:
set type=MX
set all
and see, if it has accepted your option there. If so, it should print "querytype=MX" somewhere
As it works for one user, but not for another, I assume the problem lies somewhere in the user environment (shell etc.) rather...