I came across this issue and the user's Send As permissions were there and his mailbox was not full. I tried several times to delete and replace his desktop (cmime) service book with a new copy, but I couldn't get a replacement service book to show up on the device. Finally decided to check the eventlog on the BES and it had an error “User
xxxxx@domain.com appears to be running on a BES administered with a separate database…..”
As it turns out he had been added to two different servers. I had the BES admin remove him from the BES that I didn't have access to, then I reloaded the user account on the correct BES domain. This must have prompted activation, because within 10 minutes he had a message on his bb saying “Activation complete”. After that he was able to send/receive emails and everything worked as normal.