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++ (etiquetas tu pregunta como C++ pero utilizas bibliotecas de C, y no usas ninguna característica de C++, salvo el `new empleados[2000]`): 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 MAXIMO_NUMERO_EMPLEADOS 2000
#define SUELDO_MIL 1000

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

typedef struct empleado Empleado;

struct coleccionEmpleados
{
    Empleado empleados[MAXIMO_NUMERO_EMPLEADOS];
    unsigned numeroEmpleados;
    coleccionEmpleados() : numeroEmpleados(0) {}    // Constructor C++
};
typedef struct coleccionEmpleados ColeccionEmpleados

ColeccionEmpleados coleccionEmpleados;    // coleccionEmpleados != struct coleccionEmpleados

...

void mostrarDatosMil()
{
    for (int empleado = 0; empleado < coleccionEmpleados.numeroEmpleados; empleado++)
    {
        if (coleccionEmpleados.empleados[empleado].sueldo > SUELDO_MIL) printf(...);
    }
}
```

Incluso puedes definir métodos dentro de los _structs_ para trabajar con ellos de forma más cómoda y lógica. Por ejemplo:

```
#define OPCION_MOSTRAR_MIL 3

struct coleccionEmpleados
{
    Empleado empleados[MAXIMO_NUMERO_EMPLEADOS];
    unsigned numeroEmpleados;
    coleccionEmpleados() : numeroEmpleados(0) {}    // Constructor C++
    void mostrarEmpleadosMil()
    {
        for (unsigned empleado = 0; empleado < numeroEmpleados; empleado++) printf(...);
    }
};

typedef struct coleccionEmpleados ColeccionEmpleados;

ColeccionEmpleados coleccionEmpleados;    // Llamada implícita al constructor sin parámetros

int main(int argc, char * argv[])
{
    ...
    switch (opcion)
    {
        ...
        case OPCION_MOSTRAR_MIL:
            coleccionEmpleados.mostrarEmpleadosMil();
            break;
        ...
    }
}
```

Así no tendrías métodos libres que manejen estructuras, sino que las estructuras proveen métodos para manejarlas adecuadamente.