PostgreSQL incorrectly using primary key index for min/max query

I have a table with the structure similar to this:

CREATE TABLE employees (
    id bigserial NOT NULL,
    name_id uuid NOT NULL,
    department uuid NOT NULL,
    details text NULL,
    deleted bool NOT NULL DEFAULT false,
    CONSTRAINT employees_pk PRIMARY KEY (id)
);

CREATE INDEX employees_department_and_id_index ON employees USING btree (department, id);

I need to find the highest id for the given department, the query is staightforward:

select max(id) from employees
where department = 'some-uuid';

When I query for a department with relatively small amount of total employees, the query is executed as expected with index-only scan using employees_department_and_id_index:

explain analyze select max(id) from employees
where department = '7291e1de-7870-4d68-889e-693e5731fcfb';

Result  (cost=4.58..4.59 rows=1 width=8) (actual time=0.722..0.722 rows=1 loops=1)
  InitPlan 1 (returns $0)
    ->  Limit  (cost=0.56..4.58 rows=1 width=8) (actual time=0.719..0.719 rows=0 loops=1)
          ->  Index Only Scan Backward using employees_department_and_id_index on employees  (cost=0.56..26738.12 rows=6661 width=8) (actual time=0.719..0.719 rows=0 loops=1)
                Index Cond: ((department = '7291e1de-7870-4d68-889e-693e5731fcfb'::uuid) AND (id IS NOT NULL))
                Heap Fetches: 0
Planning Time: 0.111 ms
Execution Time: 0.740 ms

However, when the condition contains a heavily-occupied department, the execution plan goes unexpectedly using employees_pk:

explain analyze select max(id) from employees
where department = 'deadbeef-deaf-feed-dead-beefdeadbeef';

Result  (cost=2.92..2.93 rows=1 width=8) (actual time=190780.059..190780.060 rows=1 loops=1)
  InitPlan 1 (returns $0)
    ->  Limit  (cost=0.56..2.92 rows=1 width=8) (actual time=190780.053..190780.055 rows=1 loops=1)
          ->  Index Scan Backward using employees_pk on employees  (cost=0.56..2257557.69 rows=959468 width=8) (actual time=190780.052..190780.052 rows=1 loops=1)
                Index Cond: (id IS NOT NULL)
                Filter: (department = 'deadbeef-deaf-feed-dead-beefdeadbeef'::uuid)
                Rows Removed by Filter: 50000000
Planning Time: 0.102 ms
Execution Time: 190780.082 ms

Notice how long it took to execute such query. Now, to force the usage of the other index, I dropped the primary key and executed this query again:

ALTER TABLE employees DROP CONSTRAINT employees_pk;
explain analyze select max(id) from employees
where department = 'deadbeef-deaf-feed-dead-beefdeadbeef';

Result  (cost=3.07..3.08 rows=1 width=8) (actual time=1.029..1.030 rows=1 loops=1)
  InitPlan 1 (returns $0)
    ->  Limit  (cost=0.56..3.07 rows=1 width=8) (actual time=1.026..1.027 rows=1 loops=1)
          ->  Index Only Scan Backward using employees_department_and_id_index on employees  (cost=0.56..2407872.31 rows=959468 width=8) (actual time=1.025..1.025 rows=1 loops=1)
                Index Cond: ((department = 'deadbeef-deaf-feed-dead-beefdeadbeef'::uuid) AND (id IS NOT NULL))
                Heap Fetches: 1
Planning Time: 0.094 ms
Execution Time: 1.047 ms

This time, the execution is a few orders of magnitude faster which clearly shows that the planner chose the incorrect primary key index.

What can be done to enforce the usage of the correct index when both of them are present? Doing analyze doesn't help here, also trying to replace max with order by id desc limit 1 doesn't change the plan.

This can be reproduced even on a clean database with the data like this – we create the layout with some small departments followed by a huge one and then more smaller departments:

create extension if not exists "uuid-ossp";

insert into employees (name_id, department)
select uuid_generate_v4(), dep.d
from 
    (select uuid_generate_v4() as d from generate_series(1, 1000)) as dep,
    (select generate_series(1, 5000)) as a;

insert into employees (name_id, department)
select uuid_generate_v4(), 'deadbeef-deaf-feed-dead-beefdeadbeef'
from generate_series(1, 1000000);

insert into employees (name_id, department)
select uuid_generate_v4(), dep.d
from 
    (select uuid_generate_v4() as d from generate_series(1, 100)) as dep,
    (select generate_series(1, 500000)) as a;

analyze employees;

I tested it on PostgreSQL 11.6, 11.8 and 12.3 on AWS RDS instance type db.m5.large with 100GB SSD storage and default parameter group, all giving similar results.
Thank you in advance for any hints how to modify the query, indexes or configuration parameters.

TL;DR: PostgreSQL doesn't use the sane index for min/max of id but prefers to seek through half of the table data using primary key index instead, which doesn't make sense.