Glad you solved it. There is a setting in the BES to also delete SHIFT deleted messages from Outlook. In BES 4.1, it is under the server properties and is called "hard deletes reconcile". If set to true, hard deletes will also delete on the devices.
Love my first BlackBerry (Pearl)!