I know that this is old but maybe my answer will help point those who need it in the right direction (I'm going through the same thing now with a company that already had an implemented AD environment).
The built-in Authenticated Users group will be granted the ability to read attributes of Active Directory objects and that will take precedence over an explicit DENY permission inherited from a parent OU / Container. It is all based on the way that AD is originally constructed and how the permission structure is designed when the forest/domain is created. Read this article for more information:
Hiding Data in Active Directory
And this one from the same series (on how to do it)...
Hiding Data in Active Directory, Part 3: Enabling List Object Mode in a Forest
Basically, you can enable List Object Mode by changing the dsHeuristics bit via ADSIedit (change the 3rd bit from 0 to 1). Then get rid of Authenticated Users (so that it isn't automatically applied to AD objects). Then your DENY permissions will take precedence. However, changing this will cause AD to require more time to evaluate permissions so be sure this is what you want to do. For "average" domains, the delay is negligible.
CAUTION: Also, be double sure that this is what you want to do (and I recommend doing this when you first build the domain, not after it is in use). Unless you do this up-front when the domain is first created, you will likely break group policies, apps that query AD, etc. This type of thing should be planned out and implemented on a domain up-front so that you ensure proper permissions are in-place for applications to work at the time they are deployed. It all depends how granular you want to get but it can easily break everything if you implement it on a domain that is already in production.