Using Personal Message search feature to search for admins - Not generating a result

I suspect that you have your settings set so that nobody can message them. Take a look there first (in the Interaction settings of the Admin group).