OK... if you did an enterprise activation, then you're on BES.
At least that part is clear.
Since you're on BES, you should have wireless sync of calendar, contacts, memos and tasks.
Again, BlackBerry Devices DO NOT SYNC MAIL... ever. You're not understanding that part
Messages are wirelessly pushed to your handheld and then reconciled.
Your email should also have two-way message reconciliation, however the details of what you can/can't do with subfolders and old messages depends largely on what version of BES you're activated on.
Is there any way you can find out from your hosting provider what version of BES they offer?
Assuming it's at least BES 4.1.6, you should be able to do a remote search from your handheld to view any messages in your Exchange mailbox, provided that you set up all of the subfolders for redirection to the handheld.