[Angel.Matilla]

Parece que encontré la solución. En lugar de preguntar si el nodo tiene hijos, pregunto cuantos hijos tiene:
Nodo = Lista->GetFirst();

while (Nodo != NULL)
{
     if (Nodo->ChildCount == 0 && Lista->CheckState[Nodo] > csUncheckedPressed)
     {
          [...]
     }
     Nodo1 = Lista->GetNext(Nodo1);
}

y parece que funciona bien. Al menos no cambia el valor de CheckState.