You can search a a pdf based on it's meta data even if it has had a policy applied to it, as long as the policy itself specified that the meta data remains unencrypted.
The Document restriction options when creating a policy include:
Encrypt all document contents
Encrypt all document contents except metadata
Encrypt only file attachments
Regards
Steve