C/C++ - Errore nel gets()

Eccomi di nuovo...
Visto che l'ultimo programma che stavo tentando di scrivere è in un momento di stallo... sono andato a ricontrollare un vecchio codificatore per XOR che avevo fatto tempo fa.
Questa è la parte fondamentale del programma:

char frase_in[1000], frase_out[1000]; 
int key;

// Code string
void codifica(char *frase) {
     for (int j = 0; j <= strlen(frase); j++) {
        frase_out[j] = frase[j] ^ key; 
        if (frase_out[j]) cout << frase_out[j];
     }
         
}   

void choice() {
    cout << "\n-[====================================================================]-";
    cout << "\nInserisci la frase da codificare:\n Frase) ";
    gets(frase_in);
    cout << "\nSeleziona la chiave di cifratura numerica.\n Chiave) ";
    cin >> key;
    cout << "\nFrase (De)codificata in chiave " << key << ":\n Frase (De)codificata) "; 
    codifica(frase_in);
}

E questo funziona egregiamente la prima volta.
Questo è l'output:

-[====================================================================]-
Inserisci la frase da codificare:
 Frase) This is a test

Seleziona la chiave di cifratura numerica.
 Chiave) 50

Frase (De)codificata in chiave 50:
 Frase (De)codificata) fZ[A↕[A↕S↕FWAF2

E tutto ok.
Se però provo a rieseguire la funzione choice(), per continuare ad inserire stringhe da codificare...
Questo è quello che succede:

-[====================================================================]-
Inserisci la frase da codificare:
 Frase) This is the first try

Seleziona la chiave di cifratura numerica.
 Chiave) 50

Frase (De)codificata in chiave 50:
 Frase (De)codificata) fZ[A↕[A↕FZW↕T[@AF↕F@K2

-[=========================================================================]-
Inserisci la frase da codificare:
 Frase)
Seleziona la chiave di cifratura numerica.
 Chiave) 50

Frase (De)codificata in chiave 50:
 Frase (De)codificata) 2
-[====================================================================]-

Praticamente non mi permette di inserire la frase_in, passando direttamente all'input della Chiave...
Pensavo in qualke particolarità del gets(), però non trovo un modo di sistemare il tutto...
Ho provato a trasformare il tutto utilizzando stringhe, ma sarebbe meglio lasciare gli array di char...
Qualke consiglio?

prova a dare un

fflush( stdin );

void choice() { 
 // ...
 cout << "\nInserisci la frase da codificare:\n Frase) "; 
 gets(frase_in); 
 cout << "\nSeleziona la chiave di cifratura numerica.\n Chiave) "; 
 cin >> key; 
 cout << "\nFrase (De)codificata in chiave " << key << ":\n Frase (De)codificata) "; 
 codifica(frase_in); 
 [b]fflush( stdin );[/b]
}