En la función "void reg_pro(propietario registro)" estás pasando una estructura que modificas en la función, sin embargo, cuando tu pasas una estructura como parámetro, lo que pasas es una copia, es decir, se copian todos los datos de la estructura para cada llamada de la función. Para modificar un parámetro, tienes que pasar la estructura por referencia, es decir, tendrías que modificar la función por "void reg_pro(propietario &registro)". Lo que haces al añadir un & es decirle al compilador que el parámetro registro se refiere al objeto que pasas como parámetro, vamos, que los cambios que hagas a la estructura de la función, se los harás en realidad al valor que hayas pasado como parámetro.

Si quieres indagar más sobre las referencias en C++, te aconsejo que te mires estos links:
http://c.conclase.net/curso/?cap=015
http://www.minidosis.org/#/actividades/Cpp.PunterosYReferencias.Referencias.vid

Espero que se haya entendido

do{
    aleatorio=(char)rand()%123;
}while(aleatorio<65 && aleatorio>122);

A ver una cosilla. El número aleatorio está entre 0 y 122, por lo que nunca va a ser mayor que 122. Lo que tendrías que hacer es calcular un número aleatorio entre 0 y la diferencia de 122 y 65, y luego sumarle 65 (aleatorio = (char)rand()%(122-65) + 65;).

También tienes que tener en cuenta que tienes que cambiar la semilla del generador de números aleatorios (rand()) con la función srand cada vez que generes un número aleatorio. Te aconsejo que uses srand(clock()).

¿Por qué en la función apilar no retornas directamente q?

Un error que he visto es el siguiente:

void mostrarPila (Pila *p){
    if(p!=NULL){
        Pila *q = p; //pila auxiliar
        while(q!=NULL){
            printf("%d ", q->dato); // Aquí interpretas el dato de q como un puntero a entero
            q = desapilar(q);
        }
        return;
    }
    printf("No hay elementos en la Pila\n"); 
} 

Pila *apilar(Pila *p, int dato){
    Pila *q = asignarMemoria(); //Pila auxiliar
    q->dato=dato; // Aquí interpretas el dato de q como un entero
    q->sgte=NULL;
 
    if(p==NULL){
        return q;
    }
    q->sgte = p;
    p = q;
    return p;
}

Básicamente, estás interpretando de dos formas diferentes una variable. O bien interpretas la variable como un puntero, o bien como un entero. En este último caso, yo cambiaría de la estructura el tipo 'int*' a 'int'

Se hace igual de como si se tratase de una variable normal. Simplemente tienes que tener en cuenta que const char* ya es un puntero, por lo que no tienes que pasar el puntero de ese puntero. scanf_s("%s", &my_class.string);  Te sobra un &

Va después de cada vez que uses scanf, fgec o demás funciones para leer datos desde la consola. Es importante que sepas por qué usas esa línea. Lo que hace esa línea es leer todos los caracteres de la consola que no se han leído por ciertas circunstancias. Por ejemplo, el que es tu caso, lees un carácter de la consola, pero cuando envías ese carácter desde la consola, estás enviando ese carácter más un carácter de fin de línea (se genera cuando pulsas enter). Entonces, cuando lees con scanf("%c", ...);, estás leyendo un carácter pero dejando el salto de línea sin leer. Por eso, después de usar scanf leemos todos los caracteres hasta que hayas leído un salto de línea.

Solo es cuestión de observación. ¿Estás usando cl/CLOCKS_PER_SEC o (cl*1000)/CLOCKS_PER_SEC? Si estás usando la primera opción, son segundos (te lo dice CLOCKS_PER_SEC), pero si estás usando la segunda  opción estás viendo milisegundos, porque estás multiplicando los segundos por 1000.

El error ocurre porque cuando tu introduces un carácter en la consola y le das a enter para confirmas, en realidad estás enviando el carácter que has escrito más el carácter de fin de línea (en C representado con '\n'). Entonces, después de leer cada carácter, tendrías que limpiar el búfer de stdin. Sé como se hace en C++, pero no en C, eso quiere decir que el código que te voy a mostrar para limpiar el búfer quizás no funcione.

while('\n' != fgetc(stdin));

Podrías generar un número aleatorio guardado en el primer elemento, y cuando calcules un número aleatorio en el segundo, si este es igual al primero, generas otro número aleatorio, y así para todas las posiciones del arreglo. Es una solución relativamente sencilla, pero no sé si será la mejor porque dependes de que te salga un número aleatorio diferente (saldrá, pero no sé después de cuántas ejecuciones)

No, el resultado está en milisegundos. Deduzco que por alguna razón te está saliendo un número negativo en la operación "cl = clock() - cl;", pero al interpretar ese número negativo como un entero sin signo, te sale ese número. Si en vez de mostrarlo como un entero sin signo lo mostraras con signo, te saldría -97 ms...

No sé por qué razón te sale un tiempo negativo... Prueba a compilar con otro compilador. Yo he compilado el código tal y como tu lo tienes y me salen resultados coherentes...