Is this server only running Sendmail? If so, then check to see if you have an increased volume of email that it is handling.

If you save the messages files or have stats on how much mail it handles, please check to see how many messages per week. If spammers have started hitting your system, this could be the only problem you are having.

You can check that you are not an open relay for spammers to use (www.abuse.net)

Next, do you have sar or any monitoring running? What is the version of Sendmail? Is it set up to use DNS? Has DNS recently changed (if sendmail is waiting on DNS, it can slow down your system as messages are not flowing as quickly waiting on timeouts from a DNS request).

Post output from % /usr/lib/sendmail -d0.1 -bt < /dev/null
(change company info as appropriate).