Creating a multi-tenant AD environment
Solution 1:
The default permissions in Active Directory aren't setup for a multi-tennant environment. You're going to have to make modifications to the stock permissions to accomplish what you're looking for. That's just the nature of the product's design.
If you can get away from a single AD forest and move to multiple account forests without trust relationships between each other (which, arguably, the Windows Server 2012 Datacenter license helps enable) you'll have to do far less "hacking" AD permissions since forests are the atomic security boundary. You would maintain resource forest(s) with one-way intransitive trust relationships to the account forests in this type of scenario.
Solution 2:
While Evan is right in that you can't really do what you want to do without hacking up permission ACLs in ADSIEdit, I thought I would go ahead and mention an alternative approach that I've used to good effect in large production environments before:
You can achieve a multi-tenant design with Active Directory using List Object Mode. Read all about it here:
https://www.myotherpcisacloud.com/post/2013/05/20/Active-Directory-List-Object-Mode.aspx
List Object mode still counts as "hacking up permissions," but it's a hell of a lot cleaner than putting Deny ACEs on everything.
Solution 3:
While you can't use your ADSIEdit method in Exchange Server 2010 or 2013 you can use the multitenant capability of Exchange Server 2010 or 2013. A far easier solution (and one that I've used with a client with similar needs) is to use Address Book Policies in Exchange Server 2010 or 2013 to provide the separation and isolation that you need.
http://technet.microsoft.com/en-us/library/hh529948(v=exchg.150).aspx