To search for a contact you need to be able to view it. If a contact can not be viewed than you can not search for it.
If you don't want an employee to see all contacts then what criteria do you want to use? Only contacts that he/she created? That is easy to do via Permission system.
Watchdog has completely different purpose - see this: http://www.epesi.org/Watchdog
Thus is it possible to create a record without watching it and then the person will not be able to access it if you set your restrictions the way you want.
What you could do is to create a multiselect field (or select) and assign a contact to an employee the same way Account Manager works for Companies. This way you will see who is a Contact Manager and then you can setup Permissions for Contact for Employee access level to view:
- Contacts created by himself/herself and
- Contact for which he/she was assigned as Contact Manager
If this is not satisfactory then please come up with a logical rule. Again - if the record can not be viewed than it can not be found.