Já precisei disto em um projeto e o que fiz foi realizar uma pesquisa antes de realizar o soft-delete. No meu caso foi tranquilo pois apenas 2 tabelas tinham relação com aquela que estava sendo manipulada.
Para trabalhar com um contexto onde você pode ter n-tabelas relacionadas, e algumas vezes tabelas de plugins ou módulos que podem ou não estar ativos, você pode criar uma classe derivada da idéia do padrão observable.
Crie esta classe com um array de modelos que devem ser consultados quando o soft-delete for ser executado. Cada modelo deve se inserir nesta classe quando instanciado/lido.
Uma forma de que o modelo se insira, em Laravel, é criar um register e no momento de registro realizar a inserção.
Desculpe não passar código de exemplo pois não terei como o fazer no momento, espero que a idéia ajude, pois Laravel não tem isso como padrão.