Salesforce.com sync with Outlook and Exchange while still using Blackberry to see contacts

Client uses Exchange 2007, Blackberry smartphones, and has some Salesforce.com users. The Salesforce sync with Outlook uses each user's contact folder to synchronize between the desktop and the cloud app. Users don't want all 5000 contacts from their contact folder sync'd with the cloud app, but until now they've been under the impression that there is no way to split their contacts into multiple folders and still have all contacts on their Blackberry. The preferred scenario would be that each Outlook user create a contact folder just for the names they want to sync with salesforce and keep all contacts from both folders on the Blackberry. The folders are not "public", although we could do something  in that arena if needed in order to get more than one contact folder to sync with the phones. Can this be done, with or without adding software to the server?