Tu error es en la función `MostarDatosMmil`, ya que la llamada a `printf` está bien, pero la comprobación no.

```
void MostrarDatosMmil()
{
    for (int k = 0; k < i; k++)    // Esto está bien
    {
        if (Cantidad[i].sueldo > sueld)    // Esto está mal
        {
            printf("\n\nNombre: %s         \nApellido: %s         \nEdad: %d          \nSueldo: %0.2f         \nGenero: %s",
                Cantidad[k].nombre, Cantidad[k].apellido, Cantidad[k].edad, Cantidad[k].sueldo, Cantidad[k].genero);
        }
    }
}
```

Estás recorriendo desde el primer elemento al último (i - 1), pero compruebas si el siguiente elemento (después del último) tiene un sueldo inferior a 1000. Esto va a tener un comportamiento indefinido, ya que las variables no se inicializan por defecto, y pueden contener cualquier valor, positivo, negativo o cero. Por lo que algunas veces te mostrará el empleado k y otras no. En cualquier caso, va a ser incorrecto porque el hecho de mostrar el empleado k depende del empleado i, que todavía no se ha metido en la colección de empleados. Es más, si llegas a llenar el vector de empleados, se intentará acceder al empleado 2001 y podrá saltar un fallo de segmento por intentar acceder a una zona que no se ha reservado.

La comprobación del `if` debería ser:

```
if (Cantidad[k].sueldo > sueld) ...
```