What is the correct procedures to clean up /var/spool/mqueue? Any help appreciated. This directory gets really clogged up at times.

The quick and easy answer is
# cd /var/spool/mqueue
# rm *

But this doesn't do a thing (except kill off all those unsent emails). If /var/spool/mqueue is not empty, then you have an issue - you need to fix the real problem of why mail isn't leaving the system.

Post the OS and version, what your network configuration is like (is this a mail relay, are you behind a firewall, running your own DNS).

You can check to see if sendmail has some errors in configuration with
# /usr/lib/sendmail -d0.1 -bt < /dev/null

It will give you something like this:

Version 8.13.4
Compiled with: DNSMAP HESIOD HES_GETMAILHOST LDAPMAP LOG MAP_REGEX
MATCHGECOS MILTER MIME7TO8 MIME8TO7 NAMED_BIND NETINET NETINET6
NETUNIX NEWDB NIS PIPELINING SASLv2 SCANF SOCKETMAP STARTTLS
TCPWRAPPERS USERDB USE_LDAP_INIT

============ SYSTEM IDENTITY (after readcf) ============
(short domain name) $w = localhost
(canonical domain name) $j = localhost.localdomain
(subdomain name) $m = localdomain
(node name) $k = localhost.localdomain
========================================================

ADDRESS TEST MODE (ruleset 3 NOT automatically invoked)
Enter <ruleset> <address>


If there are errors (this one doesn't show any), those errors need to be looked at. If it doesn't quickly give you this type of output, then you probably have an issue with DNS.