¿Por qué no simplemente crear una base de datos para cada empresa? Y luego, ni siquiera necesita construir nombres de tablas dinámicos al construir sus consultas. Es una solución mucho más sólida. Además, hará que los datos de los clientes estén más separados, por lo que cualquier interdependencia probablemente sea más obvia.
Lo anterior funciona mejor cuando las capas de la aplicación también están separadas para que pueda proporcionar a cada instancia un conjunto diferente de credenciales de inicio de sesión en la base de datos.
Si ese no es el caso, podría funcionar bien o ser incómodo o bien dependiendo de su instalación, la plataforma que esté usando, etc.
Agregar el nombre de una empresa es un truco, pero supongo que se puede hacer que funcione.
Tener una ID de cliente en los registros también es un enfoque común. No me preocuparía necesariamente por 1,5 millones de registros desde el punto de vista del rendimiento, siempre que las tablas estén indexadas de forma adecuada. Esta no es una gran cantidad de registros. Además, los criterios de identificación de la empresa deberían limitar los resultados bastante bien de todos modos.
