O que você está vendo com o problema das regras é que o sistema de regras não trata os dados atomicamente. A primeira exclusão é executada independentemente da ordem das duas instruções na regra DO INSTEAD. A segunda instrução nunca é executada, porque a linha à qual OLD.id se refere foi removida da exibição. Você pode usar um LEFT JOIN, mas isso não o ajudará por causa do design da tabela de exemplo (pode funcionar em seu esquema de banco de dados real).

O problema fundamental, a meu ver, é que você está tratando o sistema de regras como se fosse um gatilho.

Sua melhor opção é usar chaves estrangeiras e ON DELETE CASCADE em vez de regras. Com eles, seu esquema de exemplo também funcionaria:você só precisaria excluir a tabela pai para se livrar de todos os filhos.