Not sure about paypal but I'm a lawyer at at a publicly traded financial services company and all communications on company blackberries (bbm, sms) automatically get logged along with all emails. All of these communications are searchable via a system we use for discovery during litigation.

The law isn't the employee's friend here...employees have no reasonable expectation of privacy on company devices.