Eu dei uma ajeitada no codigo para coisas necessarias, mas um problema é que sempre que se cria um cadastro e exclui, se cadastrar o mesmo nome e tentar exclui-lo ele mostra como já excluido. Teria alguma maneira de ajeitar isso? so se realmente for simples. 
  
#include <stdio.h> 
#include <string.h> 
#include <conio.h> 
#include <stdlib.h> 
#include <ctype.h>  
struct registro{ 
    char nome[40]; 
    char endereco[50]; 
    char situacao[100]; 
    char tratamento[150]; 
    int dia; 
    int mes; 
    int ano; 
    int idade; 
    char status; 
} reg; 
FILE *fp;  
void abrir(char tipo[3]){  
    if((fp=fopen("Pacientes.txt", tipo))==NULL)    { 
        printf("\n O arquivo não pode ser aberto.\n"); 
        getch(); 
        exit(1); 
    } 
}  
void incluir(void){  /* função para gravar no arquivo */  
    abrir("ab+"); 
    fseek(fp,0L, SEEK_END); /* le o arquivo do inicio ao fim */  
    do{ 
        printf("\n Digite o nome do paciente ou digite FIM para sair:\n\n"); 
        gets(reg.nome);  
        if ((strcmp(reg.nome,"fim")!=0)&&(strcmp(reg.nome,"FIM")!=0)){  /* vai comparar se tem os nomes já cadastrados */ 
            printf("\n Informe o endereco:"); 
            gets(reg.endereco); 
            printf("\n Idade:"); 
            scanf("%d%*c", ®.idade); 
            printf("\n Situacao do paciente:"); 
            gets(reg.situacao); 
            printf("\n Tratamento adequado:"); 
            gets(reg.tratamento); 
            do{ 
                printf("\n Data de Ocorrencia(dd mm aaaa):"); 
                scanf("%d%*c %d%*c %d%*c", ®.dia, ®.mes, ®.ano); 
            }while(reg.ano<=1900 || reg.ano>=2100 || reg.mes<1 || reg.mes>12 || reg.dia<1 || reg.dia>31); 
            reg.status='1'; /* conta quantos protocolos existem */ 
            if(fwrite(®, sizeof(struct registro), 1, fp) != 1){  /* confere se gravou */ 
                printf("\n Erro na gravacao."); 
                getch(); 
            } 
            else{ 
                printf("\n Cadastro concluido.\n\n"); 
            } 
        } 
    } 
    while((strcmp(reg.nome,"fim")!=0)&&(strcmp(reg.nome,"FIM")!=0)); 
    fclose(fp); 
}  
int busca (void){  /* função de busca */  
    int achou=-1,posicao=0; 
    char nomep[40]; 
    abrir("rb"); 
    printf("\n Digite o nome do(a) paciente:"); 
    gets(nomep); 
    rewind(fp); /* volta pro inicio do arquivo */ 
    while((!feof(fp))&&(achou==-1)){ 
        fread(®, sizeof(struct registro), 1, fp); 
        if (!feof(fp)){ 
            if (strcmp(nomep, reg.nome)==0){ 
                if (reg.status=='0'){ 
                    posicao=-2; 
                } 
                achou=1; 
            } 
            else{ 
                posicao++; 
            } 
        } 
        else{ 
            posicao=-1; 
        } 
    } 
    if (achou==-1){ 
        posicao=-1; 
    } 
    fclose(fp); 
    return(posicao); 
}  
void consultar(void){  
    int pos; 
    pos=busca(); 
    if(pos==-1){ 
        printf("\nPaciente inexistente."); 
        getch(); 
    } 
    else 
        if(pos==-2){ 
            printf("\nPaciente inexistente."); 
            getch(); 
        } 
        else{ 
            abrir("rb+"); 
            fseek(fp,pos*sizeof(struct registro),SEEK_SET); /* percorre toda a extrutura */ 
            fread(®, sizeof(struct registro), 1, fp); /* le se tiver achado */ 
            printf("\nSituacao do(a) paciente %s: %s",reg.nome,reg.situacao); 
            printf("\nTratamento adequado: %s",reg.tratamento); 
            printf("\nData de Ocorrencia: %d %d %d", reg.dia, reg.mes, reg.ano); 
            getch(); 
        } 
    fclose(fp); 
}  
void alterar(void){  
    int pos; 
    pos=busca(); 
    if (pos==-1){ 
        printf("\nPaciente inexistente."); 
        getch(); 
    } 
    else 
        if(pos==-2){ 
            printf("\nPaciente inexistente."); 
            getch(); 
        } 
        else{ 
            abrir("rb+"); 
            fseek(fp,pos*sizeof(struct registro),SEEK_CUR); 
            fread(®, sizeof(struct registro), 1, fp); 
            printf("\nAlterar situacao do(a) paciente:%s",reg.nome);  
            printf("\nSituacao do(a) paciente: %s",reg.situacao); 
            getch();  
            printf("\nNova situacao do(a) paciente: "); 
            gets(reg.situacao);  
            printf("\nTratamento adequado: %s",reg.tratamento); 
            getch();  
            printf("\nNovo tratamento: "); 
            gets(reg.tratamento);  
            do{ 
                printf("\nNova Data de Ocorrencia(dd mm aaaa):"); 
                scanf("%d%*c %d%*c %d%*c", ®.dia, ®.mes, ®.ano); 
            }while(reg.ano<=1900 || reg.ano>=2100 || reg.mes<1 || reg.mes>12 || reg.dia<1 || reg.dia>31);  
            reg.status='1'; 
            fseek(fp,pos*sizeof(struct registro),SEEK_SET); 
            if(fwrite(®, sizeof(struct registro),1, fp)!=1){ 
                printf("\nErro no cadastro."); 
            } 
            else{ 
                printf("\nCadastro atualizado."); 
                getch(); 
            } 
        } 
    fclose(fp); 
}  
void listar(void){  
    int cont=0; 
    abrir("rb"); 
    fseek(fp, 0L, SEEK_SET); 
    fread(®, sizeof(struct registro),1, fp); 
    do{ 
        if (reg.status!='0'){ 
            printf("\nNome do(a) paciente: %s",reg.nome); 
            printf("\nEndereco: %s",reg.endereco); 
            printf("\nIdade: %d", reg.idade); 
            printf("\nSituacao do(a) paciente: %s",reg.situacao); 
            printf("\nTratamento Adequado: %s",reg.tratamento); 
            printf("\nData de Ocorrencia: %d %d %d",reg.dia, reg.mes, reg.ano); 
            cont++; 
            printf("\n"); 
        } 
        fread(®, sizeof(struct registro),1, fp); 
    } 
    while(!feof(fp)); 
    printf("\n#Numero de pacientes=%d",cont); 
    getch(); 
} 
void excluir(void){  
    int pos; 
    pos=busca(); 
    if(pos==-1){ 
        printf("\nPaciente não encontrado."); 
        getch(); 
    } 
    else{ 
        if(pos==-2){ 
            printf("\nPaciente excluido."); 
            getch(); 
        } 
        else{ 
            abrir("rb+"); 
            fseek(fp, pos*sizeof(struct registro), SEEK_SET); 
            fread(®, sizeof(struct registro), 1, fp); 
            printf("\nNome: %s",reg.nome); 
            printf("\nEndereco: %s",reg.endereco); 
            printf("\nIdade: %d", reg.idade); 
            printf("\nSituacao: %s",reg.situacao); 
            printf("\nTratamento Adequado: %s",reg.tratamento); 
            printf("\nData de Ocorrencia: %d %d %d",reg.dia, reg.mes, reg.ano); 
            printf("\nDigite qualquer tecla para excluir o registro do paciente --> %s",reg.nome); 
            getch(); 
            reg.status='0'; 
            fseek(fp, pos*sizeof(struct registro), SEEK_SET); 
            if(fwrite(®, sizeof(struct registro), 1, fp)!=1){ 
                printf("\nErro no cadastro."); 
                getch(); 
            } 
            else{ 
                printf("\nExclusao concluida."); 
                getch(); 
            } 
        } 
    } 
    fclose(fp); 
}  
int main(void){  
    char opcao[2], op; 
    do{ 
        do{ 
            system("cls"); 
            printf("\t\n\t Escolha uma das opcoes\n\n"); 
            printf("\n\t  Incluir paciente"); 
            printf("\n\t [a] Alterar cadastro"); 
            printf("\n\t [e] Excluir cadastro"); 
            printf("\n\t [c] Consultar situacao "); 
            printf("\n\t [l] Listar"); 
            printf("\n\t  Sair"); 
            printf("\n\n\n\t Opcao: \n"); 
            gets(opcao);  
            op = tolower(*opcao); 
        } 
        while( !strchr("iaecls",op) );  
        switch(op){ 
            case 'i': 
                incluir(); 
                break; 
            case 'a': 
                alterar(); 
                break; 
            case 'e': 
                excluir(); 
                break; 
            case 'c': 
                consultar(); 
                break; 
            case 'l': 
                listar(); 
                break; 
            case 's': 
                exit(0); 
        } 
    } 
    while(1); 
}