Por que não apenas criar um banco de dados ou cada empresa? E então você nem precisa construir nomes de tabelas dinâmicas ao construir suas consultas. É uma solução muito mais sólida. Além disso, tornará os dados do cliente mais separados, de modo que qualquer interdependência provavelmente será mais óbvia.

O acima funciona melhor quando as camadas do aplicativo também são separadas para que você possa fornecer a cada instância um conjunto diferente de credenciais de login do banco de dados.

Se não for esse o caso, pode funcionar bem ou ser estranho ou bem dependendo da sua instalação, qual plataforma você está usando e assim por diante.

Acrescentar um nome de empresa é um hack, mas pode ser feito para funcionar, eu acho.

Ter um ID de cliente nos registros também é uma abordagem comum. Eu não me preocuparia necessariamente com 1,5 milhão de registros do ponto de vista do desempenho, desde que as tabelas sejam indexadas apropriadamente. Esta não é uma grande quantidade de registros. Além disso, os critérios de identificação da empresa devem limitar os resultados muito bem de qualquer maneira.