Lo que tienes que hacer es dejar la mesa como está. Tiene razón, debe almacenar la información del cliente en la factura para el historial de dónde se enviaron los artículos. Cuando cambie, NO debe actualizar esta información, excepto las facturas que aún no se hayan enviado. Para mantener este tipo de información, necesita un activador en la tabla de clientes que busque facturas que no se hayan enviado y actualice esas direcciones automáticamente.
Si desea guardar versiones históricas de la información del cliente, el proceso correcto es crear una tabla de auditoría y completarla a través de un disparador.
La integridad de los datos en este caso es simplemente a través de una clave externa a la identificación del cliente. La identificación en sí nunca debe cambiar ni el usuario debe permitir que cambie y debe ser un número sustituto, como un número entero. Debido a que no debe cambiar la información de la dirección en la factura real (a menos que no se haya enviado, en cuyo caso será mejor que la cambie o el producto se enviará al lugar equivocado), esto es suficiente para mantener la integridad de los datos. Esto también le permite ver dónde se envió realmente el material, pero aún así buscar la información actual sobre el cliente mediante el uso de la clave externa.
Si tiene clientes que cambian (compañías compradas por otras compañías), puede ejecutar un proceso en el servidor para actualizar la identificación del cliente de registros antiguos o crear una estructura de tabla que muestre qué identificaciones de clientes pertenecen a una identificación principal actual. El primero es más fácil de hacer si no está hablando de cambiar millones de registros.