Problema com modelagem do banco

Olá senhores. Estou com um problema na modelagem e gostaria de conselhos / dicas para como resolver.
Meu chefe me deu a incumbência de remodelar o banco para ser único para todas as empresas que contratam os nossos serviços.
Minha dúvida vem agora. Como cadastrar itens únicos dessa forma?
exemplo. Se eu vou na sapataria do Fulano, que usa o programa, e compro um sapato e peço a nota fiscal, eles cadastram meu nome com CPF e sai a nota. Depois se vou na Loja de Roupas do Cicrano e compro roupas e peço a nota, na hora de cadastrar meus dados, dará que cpf ja existe.
Agora, como proceder?
Pensei em, ao inves do campo CPF ser único, o campo CPF + id_empresa será unico, dessa forma so podera ter um CPF na empresa X, mas o mesmo CPF podera ser cadastrado na empresa Y caso esse CPF nao exista na empresa Y.
Essa seria a melhor forma?

Sugestao, considerando um cenário bem simples:

Tabela Cliente: id_cliente (PK), cpf (unique key), etc
Tabela Venda: id_venda (PK), id_empresa (FK), id_cliente (FK), data, etc
Tabela Item_Venda: id_venda (PK, FK), id_produto (PK, FK), quantidade, etc