We are in a BES environment including Exchange 2003 SP2. We have one user out of 90 that can receive email on his handheld but can not send email. And unfortunately the status shows unknown error. We've installed all BES patches, etc.

Sounds like their encryption key has expired. Can they get to a PC, creadle it and start Desktop Manager. Go into Redirector Settings and find the area to generate a new encryption key.

Re-send down the service books to that handheld?

Yeah...sounds to me like their Desktop (CMIME) service book needs to either be resent, or deleted/undeleted.