Change quick search ACL from "Access CiviCRM" to "Edit all Contacts"
Time for a custom extension! I'd 
hook_civicrm_navigationMenu this bad boy - just hiding it in the JS won't help you from a security perspective.