Il tuo è un buon programma. Lo definirei più "C" che "C++", ed è vero, hai evitato l'uso di puntatori.

Mi chiedevo invece se non fosse il caso di cercare di trasformare l'applicazione in qualcosa che usi "classi/oggetti" in una "collezione" piuttosto che impiegare un puntatore fine a se stesso.

Col puntatore potresti ingradire dinamicamente la dimensione dele voci contenute nella rubrica (ora limitata a 50). Oppure, trasformare la struttura "rubrica" in qualcosa che sia una lista o un tree (tree magari per tenere gli elementi ordinati sin dell'inserimento senza invocare poi una funzione di "ordinamento" - molto bello invece il fatto che fai uso della ricerca binaria, complimenti).

Gli elementi stessi dichiarate nella struttura "rubrica" potrebbero essere a sua volta dei puntatori (sono tutte degli "array" di caratteri), ma questo ricorda molto più il "C" e le metodologie di lavoro "unsafe" che non C++ dove si andrebbe invece ad impiegare la classe "string" o "wstring" (al posto degli array di caratteri).

Comunque nel codice ci sono delle note di programmazione "unsafe" (questa parola indica l'impiego di celle di memoria al di fuori del loro dominio applicativo; il C ed il C++ consentono questa pratica ed è spesso la causa di molti problemi che richiedono una montagna di tempo per essere scovati).

Ad esempio nella funzione "aggiunta" dichiari un'array di caratteri "char strin[15];" di 15 elementi.
Ora... è vero che ad un certo punto fai questi controlli:

codice:
if (strlen(strin)>15)  //controllo lunghezza
{
     flag=1;
     printf(".... troppo lungo, inserire di nuovo\n");
}
ma se fossero vere queste righe di codice, allora la variabile "strin" è già stata "sfondata", in quanto essa può contenere in modo "safe" 14 caratteri validi (il 15cesimo dovrebbe fungere da terminatore di stringa contenendo '\0'). L'impiego dell'array oltre al 15cesimo carattere è considerato "unsafe" perchè andrebbe a sovrascrivere celle di memoria dedicate ad altre "cose" (variabili o al codice stesso).

poi te la butto lì... una ricerca di tipo "wildcard compare", ossia facendo uso dei caratteri "*" e "?" come per per il comando DIR del DOS... Qui c'è l'esempio di uno che ha scritto una funzione a questo scopo: http://www.codeproject.com/string/wildcmp.asp - l'alternativa sarebbe quella di usare le "regular expressions" che però sono un po' più complesse.

I miei più sinceri complimenti per la completezza e l'attenzione a molti particolari in fase di programmazione. Complimenti per l'impiego della ricerca binaria.