Não há definição formal e duvido que um dia vá existir (é sintomático que não exista verbete na Wikipedia). Ele é subjetivo. Sempre que alguém disser o que é, desconfie. Mas é claro que algumas observações podem ser feitas independente de opinião. É óbvio que elas são vagas e não vão ajudar muito a definir com clareza o que é o termo, mas também não farão presunções tendenciosas.
- O fluxo de execução da aplicação é facilmente entendível, não importa em que paradigma, (não entenda fluxo só como o fluxo imperativo).
- Os diversos objetos (nada a ver com OOP) tem relacionamento claramente definidos e é fácil percebê-los.
- O papel e responsabilidade de cada participante da aplicação (classes, funções, variáveis, etc.) são claros, possivelmente com nome bem escolhido.
No momento não consigo lembrar de nada mais que não seja específico e subjetivo demais para ser aplicado como uma forma geral de entendimento do assunto.
Então o código precisa:
- Ser fácil de entender por quem nunca o tinha visto antes.
- Possibilita manutenção sem grandes sobressaltos.
- Funciona corretamente.
Claro que espera-se que o leitor do código seja um desenvolvedor capacitado, quem entenda bem a linguagem onde está escrito e entenda os fundamentos da computação. A não ser que um código seja escrito para fins didáticos não é obrigação do código limpo explicar de qualquer forma seu funcionamento para leigos (mesmo aqueles que são remunerados como desenvolvedores, isto existe, e muito).
Aí podemos começar definir algumas coisas mais específicas que ajudam cumprir estes três requisitos destacados acima:
- As unidades de código devem ser curtas e ter apenas uma responsabilidade.
- As partes "públicas" (a API) devem ser claras (óbvias, sem surpresas) e concisas (faz o mínimo necessário).
- As estruturas de dados e algoritmos devem funcionar como o esperado.
- O código deve ser facilmente verificável.
- Códigos devem ser organizados e expressivos (concisamente indica a sua intenção)
Além disto provavelmente está indo além da definição básica e começa entrar no campo subjetivo.
Eu até usei uma fonte bem recente para escrever esta resposta. Nem vou citá-la porque o meu texto está suficientemente diferente e o original induz à ditadura do mono paradigma que tão bem o AP renegou. Paradigmas não são mágicos, não resolvem problemas. São ferramentas que podem ser mais ou menos adequados.
O primeiro capítulo do livro está disponível como artigo. Conforme o livro vai se aprofundando ele vai sugerindo certas coisas que são discutíveis. O livro não é ruim, todo mundo deveria lê-lo, porém quem não está suficientemente preparado acaba comprando indiscriminadamente algumas técnicas, no mínimo, duvidosas.
Na pergunta que foi citada pelo AP eu faço uma análise rápida do livro e outro que trata de assunto semelhante.
Só um adendo para não passar a falsa impressão que 100% do código escrito deva ser limpo. Claro que isto seria ideal mas há certos domínios em conjunto com certos requisitos que conflita com o conceito de código limpo. Pode ser raro, não ser aplicável em determinados tipos de projeto, mas existem situações assim. Como em tudo, você deve saber quando perseguir um ideal e quando ser pragmático e resolver o problema da forma mais adequada.
Coloquei no GitHub para referência futura.