To add some detail to Joe's answer:
One possible reason a started task may be reading a dataset, even though the dataset has no owner and no permissions, is that the ACID that runs the started task has NODSNCHK, an attribute whose meaning I suppose you can figure out. The manual says that really should be assigned only during disaster recovery, and I heartily agree, but I've seen it applied distressingly frequently to machine (not human) IDs. Very sloppy in my opinion.
Another possibility is if the STC list in TSS has assigned "*BYPASS*" (instead of a real ACID) to the particular started task, or if the proc isn't defined in the STC list and the default value is *BYPASS*. Such STCs are allowed all access—security checks are bypassed, in other words.
You can look at the STC definitions by doing a LIST command on "STC" as if it were an ACID.
As Joe hinted, "RDT" is another entity you can list as if it were an ACID. That'll show you a definition of every resource class. I keep thinking the DEFACC field shown there is the default access level for a resource that isn't defined, but it ain't so; I believe DEFACC is actually the access level that is assumed during a PERMIT command if you don't specify.
Profile order: In most TSS installations I've worked at, the profile order does matter. This is both a strength and a complication; it allows you lots more power in controling access, but it also can result in unexpected interferences. I've written a few REXX programs for this problem, for example one that lists all users that have two profiles in the "wrong" order, so I can find and fix them once I've discovered the problem. As Joe said, there's a TSS parm that controls whether the profile order is important; when it does, TSS searches first the user's list of "direct" permissions, then the permissions of each profile one by one, then the ALL record, and stops looking when it finds a match. I regard this behavior as normal, but your installation may be using a different AUTH setting.