Update 10/3/2014: This article was updated to include new defaults/limits information for Office 365 for Enterprise.
Since we added the Address Book Policy feature in Exchange Server 2010 Service...
Updated Jul 01, 2019
Version 2.0
Blog Post
Sam - we tested up to 50k tenants with 2010. Are you seeing specific issues or is this just a theoretical question?
Arjen - thanks for the feedback, and we considered it briefly for this, but it's a hard problem to solve and so didn't get to it yet. It will not be in CU2, so don't expect it. It may happen one day, but likely it may not. You can always use a trabsport rule to delete OOF's - I know that deletes all OOF's, but that's the only suggestion I have for you right now.