If you have permissions set correctly so that they can view top -> down each forum category, forum, topic, etc... then I would try rebuild your search index. Maybe something is wrong but if you continue to see a search for the same term available on one account but not another, we would need to review that further with the term, the accounts, and the topic(s) you believe they should see.