Some questions :
Did you resend the service books to the devices?
Did you regenerate the encryption key on the devices?
Do the devices receive an error when they try to send?
I always try to start with:
Is the device still active EDGE/GPRS (in capitals) 3G/....
Does a resend of the service books helps.
Does the BB receives an error when sending a mail?
Does PIN to PIN messages work?
...
The last step is wipe and redo an enterprise activation.
In most of the times this is an overkill for solving this kind of problem. Sometimes it's the only solution you have.
Kurt