Isso acontece porque stdin pode ser bufferizado ou não, dependendo da configuração específica do terminal. De fato, a manpage sobre gets recomenda NÂO usar gets() por ser sucetível a buffer overuns. As observações sobre stdin na manpage 'stdin' (livro 3) falam sobre a bufferização de stdin.
É recomendável, neste caso, o uso de scanf() para ler a string, inclusive especificando o tamanho máximo da string (19 chars, no seu caso):
scanf("%19s", empregados[i].nome);
Outra coisa... fazer flush de stdin não adianta muita coisa, já que o flush é, provavelmente, feito a partir do momento em que vocẽ digita o <ENTER>. O fflush será útil, no entanto, se você o fizer sobre o stdout, já que ele é bufferizado por linha - isto é, o buffer só será descarregado (flushed) automaticamente se for encontrado um '\n' ou quando o buffer ficar cheio.
Assim, troue seu gets() pelo scanf(), como mostrado acima, e troque seus "fflush(stdin)" por "fflush(stdout)".
[]s
Fred