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) ...
```

En cualquier caso, considera seguir las convenciones de C/C++ (dices que tu código es C++ pero utilizas bibliotecas de C, y no usas ninguna característica de C++), como escribir el **nombre de funciones y variables empezando con minúscula** (_lower camel case_ por ejemplo), y los `#define ALGO` en mayúscula (sin empezar por guiones, ya que estos tienen un uso reservado al compilador).

Además, te recomiendo que no declares una variable global llamada `i` porque su nombre no significa nada. Considera **refactorizarla como `numeroEmpleados`** por ejemplo, y poner nombres de variables completos y significativos.

Además, una variable de tipo `struct empleados` no va a contener muchos empleados, sino uno, por lo que te recomiendo poner el nombre en singular.

Para un mayor orden y corrección sería incluso mejor declarar otra estructura, que contenga la colección (vector) de empleados y el número de empleados insertados hasta el momento.

```
#define SUELDO 1000

typedef struct
{
    char nombre[30];
    char apellido[30];
    int edad;
    float sueldo;
    char genero [15];
} Empleado;

typedef struct
{
    Empleado[] empleados;
    unsigned numeroEmpleados;
} ColeccionEmpleados;
```