The problem is usually in the size of the Call Logs and the SMS Logs.
Connect to the Desktop Manager and click on Backup and Restore >Advanced. Now the column on the right contains all of the BlackBerry's currently installed Databases. Scroll down until you see "Call Logs" then hit the Clear button, then scrol down til you see SMS, then hit the Clear button.
If your BlackBerry is a Pearl, Curve, 8800, 8830 or newer then from the main screen click on Media >Pictures > click the menu button to the left of the trackball and go to "Options" from options you will see the Device Memory Limit - select the number that you see (probably 20mb) and change it to 12mb by selecting it, then clicking the menu button and choosing EDIT. Next you should see your Picture Memory Limit (on some devices) and you will want to set that to 5mb. If you notice that the values haven't changed then this is because they have already been surpassed, and some pictures and or ring tones may have to be deleted.
If your boss surfs the internet on his handheld then you may have to clear the browser cache and cookies. Open the browser, click on the menu button (or trackwheel) and go to Options >Cache Operations > then clearing everything.
If he still has problems, you could try uninstalling unneeded applications, such as languages, TTY support, brick breaker, instant messaging programs.. etc
These steps should clear up enough space for your boss to work for a while.