Our users are experiencing red x's but some of those messages really went thru. I have heard about a bug in OS 4 which is what we use. Does dbclean.exe resolve the red x's and possible slowness of emails both receiving and sending?

Open a message with the red X. Scroll up to Message Status. What is the status? Do your users happen to be using AT&T BlackBerries? There is an issue with AT&T network today. I they are on AT&T, you might want to wait before making too many changes.