Thiago bom dia,
Para sanar o problema da exclusão no sentindo oposto, você pode utilizar a configuração de ON DELETE CASCADE que resolveria, você só precisaria tratar no VB6 para caso ele tente deletar e não tenha nada ele não acuse erro.
Com relação a sua dúvida de performance, depende da quantidade de dados que estamos falando, a questão de FK e PK, ajuda muito em performance, mas você tem que avaliar o custo beneficio de uma mudança dessas, faça um backup do banco e aplique alguns testes
para ver em produção o resultado.
Att
Guilherme Silva Cardoso