Blackberry remote search capabilities

We just swapped a user to a new blackberry and they seemed to have lost their ability to remotely search email from the exchange server vs. locally on their blackberry.  I am fairly new to supporting black berry and from what I googled, I can't seem to find a definitive answer to how to fix this.  

This is a blackberry user on BES.   blackberry model 9300, software 5.0.0.846 (Platform 6.3.0.39).  We DO apply custom security policies to this device.  I am not sure if that is the problem and I need to change an option in the policy to allow for this or there is some other issue going on.   I have tested on my own black berry and confirmed I am not able to do this either.  

I am hoping someone in the community can help solve this.  

thanks!