Acho que, na maioria dos casos, as diferenças entre os dois serão pequenas o suficiente para que a escolha seja orientada principalmente pela escolha da implementação que acaba sendo mais compreensível para alguém que está olhando o código pela primeira vez.

No entanto, acho que o tratamento de exceções tem algumas pequenas vantagens:

• 
  O tratamento de exceção evita uma possível condição de corrida. O método 'verificar e inserir' pode falhar se outro processo inserir um registro entre sua verificação e sua inserção. Portanto, mesmo se você estiver fazendo 'verificar e inserir', ainda deseja o tratamento de exceções na inserção e, se já estiver fazendo o tratamento de exceções de qualquer maneira, também poderá eliminar a verificação inicial.
  
• 
  Se o seu código não for um procedimento armazenado e tiver que interagir com o banco de dados através da rede (ou seja, o aplicativo e o banco de dados não estiverem na mesma caixa), você deseja evitar duas chamadas de rede separadas (uma para a verificação e a outra outro para a inserção) e fazê-lo via tratamento de exceção fornece uma maneira direta de lidar com tudo com uma única chamada de rede. Agora, existem várias maneiras de fazer o método 'verificar e inserir' enquanto ainda evita a segunda chamada de rede, mas simplesmente capturar a exceção provavelmente será a maneira mais simples de fazer isso.
  

Por outro lado, o tratamento de exceções requer uma restrição exclusiva (que é realmente um índice exclusivo), que vem com uma compensação de desempenho:

• A criação de uma restrição exclusiva será lenta em tabelas muito grandes e causará um impacto no desempenho em cada inserção dessa tabela. Em bancos de dados realmente grandes, você também precisa fazer um orçamento para o espaço extra em disco consumido pelo índice exclusivo usado para impor a restrição.
• Por outro lado, pode tornar a seleção da tabela mais rápida se suas consultas puderem aproveitar esse índice.

Eu também observaria que, se você estiver em uma situação em que o que realmente deseja fazer é 'atualizar outra inserção' (ou seja, se já existe um registro com o valor exclusivo, você deseja atualizar esse registro, senão insere um novo record), então o que você realmente deseja usar é o método UPSERT do seu banco de dados específico, se houver um. Para SQL Server e Oracle, isso seria uma instrução MERGE.