Couple of things jump right to mind:
– By chance, do these users have the *ALLOBJ special authority in their profile, or belong to a group that does? If so, that trumps any other authority rules you may be trying to implement.
– How are they accessing these queries? By chance, would it be from a CL that runs with adopted authority, or within some sort of program menu structure that utilizes adopted authority, a la BPCS or Jack Henry? If so, that might be running as some other user that the one you think.
Just the first two things that come to mind.