When a Permission Set is set to "Deny" by default for "Menus & Pages / Urls", any User who uses that Permission Set will be denied access to search the Wiki. This can be easily corrected by adding Permissions to the Wiki Specific URLs.
Add the following Permission to the impacted Permission Sets:
- Page: Default
- URL: wikihelp
- Allow: yes
Once applied, these Users will be able to access the Wiki.