HI Katie,
I would start creating landing page domains and branding domains for each of your customers, which will required that each if your customers add some entries in their DNS.
Second, creating specific opt-in per company is not that difficult, you will need a series of fields (one for each of the brands) to be added to each form and potentially opt-in programs if you need to manage double opt-in.
I would formalize all these steps in a roll out guide where you will have to list all the items that have to put in place when you add a new subsidiaires / brands.
You could also consider using partitions and workspaces to separate the databases and limit the risks, though. But this option needs to be implemented with care if you need to share some of the persons in the DB between multiple subsidiaries.
The very hard point with opt-in is to enforce it when launching the campaigns, at least until this idea is implemented. This will require some thorough discipline around your users, so training and documentation will be important
-Greg