Postgres, Simple Queries not using index

PostgreSQL 9.5.0

I have a table called message_attachments it has 1931964 rows.

There's one key that I search for in that table, that's message_id.

I also, always include the deleted_at is NULL statement (e.g. soft delete).

There was an index created:

CREATE INDEX message_attachments_message_id_idx 
   ON message_attachments (message_id) 
WHERE deleted_at IS NULL;

So it should directly match this query:

EXPLAIN ANALYZE 
select * 
from "message_attachments" 
where "deleted_at" is null 
  and "message_id" = 33998052;

But the resulting query plan looks like this:

Seq Scan on message_attachments  (cost=0.00..69239.91 rows=4 width=149) (actual time=1667.850..1667.850 rows=0 loops=1)
   Filter: ((deleted_at IS NULL) AND (message_id = 33998052))
   Rows Removed by Filter: 1931896
 Planning time: 0.114 ms
 Execution time: 1667.885 ms

I'm using such indices through out my database, but somehow it seems that it doesn't like it on that specific table.

Regarding cardinality, there's at most 5 columns with the same value.

Also a ANALYZE and VACUUM ANALYZE was run on that table.

Edit 1

SET enable_seqscan to off

SET enable_seqscan to off; EXPLAIN ANALYZE select * from "message_attachments" where "deleted_at" is null and "message_id" = 33998052;
SET
                                                                           QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on message_attachments  (cost=36111.83..105378.49 rows=4 width=149) (actual time=2343.361..2343.361 rows=0 loops=1)
   Recheck Cond: (deleted_at IS NULL)
   Filter: (message_id = 33998052)
   Rows Removed by Filter: 1932233
   Heap Blocks: exact=45086
   ->  Bitmap Index Scan on message_attachments_deleted_at_index  (cost=0.00..36111.82 rows=1934453 width=0) (actual time=789.836..789.836 rows=1933784 loops=1)
         Index Cond: (deleted_at IS NULL)
 Planning time: 0.098 ms
 Execution time: 2343.425 ms

This would be running now on the second index on that table, which looks like that: (and should definitely NOT be used)

CREATE INDEX message_attachments_deleted_at_index ON message_attachments USING btree (deleted_at)

Edit 2

\d+ message_attachments
                                                         Table "public.message_attachments"
   Column   |            Type             |                            Modifiers                             | Storage  | Stats target | Description
------------+-----------------------------+------------------------------------------------------------------+----------+--------------+-------------
 id         | bigint                      | not null default nextval('message_attachments_id_seq'::regclass) | plain    |              |
 created_at | timestamp without time zone | not null                                                         | plain    |              |
 updated_at | timestamp without time zone | not null                                                         | plain    |              |
 deleted_at | timestamp without time zone |                                                                  | plain    |              |
 name       | character varying(255)      | not null                                                         | extended |              |
 filename   | character varying(255)      | not null                                                         | extended |              |
 content    | bytea                       |                                                                  | extended |              |
 hash       | character varying(255)      | not null                                                         | extended |              |
 mime       | character varying(255)      | not null                                                         | extended |              |
 size       | bigint                      | not null                                                         | plain    |              |
 message_id | bigint                      | not null                                                         | plain    |              |
Indexes:
    "message_attachments_pkey" PRIMARY KEY, btree (id)
    "message_attachments_deleted_at_index" btree (deleted_at)
    "message_attachments_message_id_idx" btree (message_id) WHERE deleted_at IS NULL
Foreign-key constraints:
    "message_attachments_message_id_foreign" FOREIGN KEY (message_id) REFERENCES messages(id)

Edit3

Exactly the same behaviour on a hot standby host. (it is up2date)

Edit4

select seq_scan,seq_tup_read,idx_scan,idx_tup_fetch,n_live_tup,pg_stat_all_tables.n_dead_tup,last_analyze,pg_stat_all_tables.analyze_count,pg_stat_all_tables.last_autoanalyze from pg_stat_all_tables where relname = 'message_attachments';
 seq_scan |  seq_tup_read  | idx_scan | idx_tup_fetch | n_live_tup | n_dead_tup |         last_analyze          | analyze_count |       last_autoanalyze
----------+----------------+----------+---------------+------------+------------+-------------------------------+---------------+-------------------------------
 18728036 | 26379554229720 |  1475541 |     808566894 |    1934435 |      28052 | 2017-04-12 09:48:34.638184+02 |            68 | 2017-02-02 18:41:05.902214+01

select * from pg_stat_all_indexes where relname = 'message_attachments';
 relid  | indexrelid | schemaname |       relname       |             indexrelname             | idx_scan | idx_tup_read | idx_tup_fetch
--------+------------+------------+---------------------+--------------------------------------+----------+--------------+---------------
 113645 |     113652 | public     | message_attachments | message_attachments_pkey             |  1475563 |    804751648 |     802770401
 113645 |     113659 | public     | message_attachments | message_attachments_deleted_at_index |        3 |      5801165 |             0
 113645 |   20954507 | public     | message_attachments | message_attachments_message_id_idx   |        0 |            0 |             0