Multi-tenant database
100,000 tenants, so we're anticipating average of 20,000 companies per tenant and 40,000 people per tenant. Hosted in Azure using SQL Azure Federation services


You do realize that your number comes up to 2 billion entries?

I'm afraid the answer is that there are several ways to accomplish what you want to achieve.  You can have a master table with your company information and then sub tables containing the users under each company.  Keep in mind on incoming queries, the more joins you have to make, the longer the response time.  

This is a massive design effort that will not be easily answered in this format and should be reviewed by a design team in several disciplines.

I would recommend splitting them into different logical groups either by tenant, company etc.... The main reason being any DUI ( Delete, Update, Insert) will lock the records as it runs which can potentially cause problems