View not showing most results for some roles, but content is not restricted

EDIT: The view has a relationship and if I remove this, the "normal user" role can get all the results the same as for the admin user. Nodes showing for the normal user seem to be the ones where there is some positive result for the relationship. I still don't understand though why this could be causing the problem, as the field in the relationship is visible to the "normal user" role.

ORIGINAL ISSUE:
I have a view with three exposed filters set to show results for one content type. The whole view is restricted to certain roles. Many nodes exist with the same text string in the node title. If an admin or "manager" (semi-admin) searches on this string they see results for hundreds of nodes, which is correct. If the user has a "normal user" role with fewer permissions and runs the same search they only get a handful of results. Some fields in the content type are restricted using Field Permissions, but all nodes of the type are still technically visible to the "normal user", so in other words if this user navigates manually to a node that did NOT show up in the search results, they can still view the node. I've looked through the nodes that do show up, the ones that don't, the content type settings, the view settings, the permissions, but nothing seems obvious. One thing that rectified the problem was giving the "normal user" the "Bypass content access control" permission, which the "manager" role also has, but that's not an acceptable solution as the "normal user" can't have that degree of control. What could be causing this?