NQUEUE on local host is normal But if people can't send what is your load average on your machine ? are you getting like connection refused ? telent in and type w is it above 3 % also have you tried restarting sendmail /etc/rc.d/init.d/sendmail restart
Sendmail's website says the following about NOQUEUE: NOQUEUE: Null connection from host.domain [IP.AD.DD.RESS]