Also, keep in mind:
"We use BlackBerry Enterprise Server 4.1.4 (upgraded from version 4.1.1) on Windows Server 2003 with SQL 2005. The Server specs: are Pentium 4 CPU 2.8 GHz, RAM 1GB, HD 40 GB (15 GB Space Left)."
BES and SQL on the same box with only 1GB of RAM, either way upgrade the to 2 GB. BES documentation states a minimum 1.5 when the BES is a standalone machine. SQL is known to be a resource hog. How many users are you supporting? Is the Exchange/Domino/GroupWise on the same box as well? You didn't clarify what mail platform you are using.
When they can't reply what does the Using field of the message show? Desktop Secure? Unknown?
If it shows Unknown then the service book is corrupt and re-sending it should correct it but if it's a reoccurring issue then something else is going on.
For users that show an IT Policy status of Error you will more than likely have to reactivate because the BB is rejecting the Policy and will not accept a new one until you perform a security wipe.