Pues la primera vez funciona y el resto no porque simplemente el for modifica el valor hasta 10 y luego tu no lo seteas a 0 para que vuelva a buscar en todo el puntero. Tu bucle for y el if...else son deficientes, necesitas mejorarlos. Si aun asi no funciona no estaria mal que probaras con un switch en vez de if.

int salir = 0;
char pregunta[3];
 
//Mientras salir sea 0 seguimos con el bucle
while(salir==0) {
    //Comparamos nombre[i] y aux
    switch(strcmp(nombre[i],aux)){
        case 0: //En caso de que haya correspondencia
            printf("El nombre se encuentra entre los anteriores\n");
            salir++;
            break;
        default:
            i++;
            break;
    }
    while(i==10) {
        //Si es 's' lo repite, cualquier otra cosa termina el bucle
        printf("Desea volver a buscar? [s/*]");
        gets(pregunta);
        switch(strcmp(pregunta,"s") {
            case 0:
                salir=0;
                i=0;
                break;
            default:
                salir++;
                break;
        }
    }
}

Esto es lo que hubiese intentado yo en tu caso, aunk no lo he probado aun xd. Ciertamente este código no te avisa si estas equivocado, pero eso es lo minimo. Pues analizalo y crea tu propio algoritmo, esto es una idea de lo que mas o menos podrias hacer y recalco: no lo he probado.
Este codigo necesita de las declaraciones y el primer for. Un consejo: yo uso for solo cuando es necesario, si te produce problemas cambialo y usa otro bucle que te de mas libertades.
Saludos.