In your permissions, for each page you are expecting to see under Add Listing search, the relevant permissions needs both of the following to be set to Yes:
- Can view list of categories containing this ....
- Can put ... in Categories
"Can put in categories" without "can view list of categories" is like having permission to edit a page without having permission to view the page. Simply put, we don't allow that.