Acontece que o serviço rhnsd simplesmente continuou tentando se conectar ao RHN porque ele não pôde se conectar. Quando o serviço foi interrompido, houve várias consultas ao DNS que foram "enfileiradas" e elas continuaram por mais alguns minutos depois que o serviço foi interrompido, e foi por isso que parecia que ele não teve nenhum efeito. Eu esperei 1 hora depois que o serviço foi interrompido e depois de um tempo as perguntas pararam completamente e não voltaram.
Então, tudo o que eu tive que fazer foi parar e desativar os serviços rhnsd e rhsmcertd e esperar alguns minutos.