Si un programa escrito en C no se puede descompilar, ¿cómo pueden otros descifrar el software pago y hacerlo gratuito?

La llamada no descompilación es relativa, no absoluta. Por lo general, significa que no se puede obtener el código fuente del programa;

El software de descifrado encuentra directamente el salto correspondiente en el código binario y luego lo descifra, pero no puede obtener el código fuente del programa; omite el proceso de verificación.