sudo define os uids reais e efetivos. Tornar um executável setuid apenas faz com que o uid efetivo seja definido quando o executável é executado. Se o executável manipula uids para bifurcar filhos desprivilegiados como dhclient, você pode facilmente desabilitá-lo executando-o com um uid real não-root.
Uma solução seria escrever um executável de wrapper que não faça nada além de definir o uid real para corresponder ao uid efetivo e, em seguida, executar o dhclient. Faça o wrapper setuid root e remova o bit setuid do dhclient.