O que você precisa fazer é deixar a mesa do jeito que está. Você está correto, você deve estar armazenando as informações do cliente na fatura para o histórico de onde os itens foram enviados. Quando isso mudar, você NÃO deve atualizar essas informações, exceto para quaisquer faturas que ainda não foram enviadas. Para manter esse tipo de informação, você precisa de um gatilho na tabela de clientes que procure as faturas que não foram enviadas e atualize esses endereços automaticamente.

Se você deseja salvar versões históricas das informações do cliente, o processo correto é criar uma tabela de auditoria e preenchê-la por meio de um gatilho.

A integridade dos dados neste caso é simplesmente por meio de uma chave estrangeira para o ID do cliente. O id em si nunca deve ser alterado ou ter permissão para ser alterado pelo usuário e deve ser um número substituto, como um inteiro. Como você não deve alterar as informações de endereço na fatura real (a menos que não tenha sido enviada, nesse caso é melhor alterá-la ou o produto será enviado para o local errado), isso é suficiente para manter a integridade dos dados. Isso também permite que você veja onde o material foi realmente enviado, mas ainda procure as informações atuais sobre o cliente por meio do uso da chave estrangeira.

Se você tiver clientes que mudam (empresas compradas por outras empresas), você pode executar um processo no servidor para atualizar o ID de cliente de registros antigos ou criar uma estrutura de tabela que mostre quais IDs de cliente pertencem a um ID pai atual. A primeira é mais fácil de fazer se você não estiver falando em alterar milhões de registros.