Uma solução possível é simplesmente usar DROP IF EXISTS antes de criar a nova restrição.
ALTER TABLE foo DROP CONSTRAINT IF EXISTS bar;
ALTER TABLE foo ADD CONSTRAINT bar ...;
Parece mais fácil do que tentar consultar information_schema ou catálogos, mas pode ser lento em tabelas enormes, pois sempre recria a restrição.
Editar 2015-07-13:Kev apontou em sua resposta que minha solução cria uma janela curta quando a restrição não existe e não está sendo aplicada. Embora isso seja verdade, você pode evitar essa janela facilmente envolvendo ambas as instruções em uma transação.
