Emulating your setup

I think your index is badly maintained. That's about all I can come up with. I tried and emulated everything with 50 M rows.

CREATE TABLE messages
AS
  SELECT
    x::int AS conversation_id,
    ((x::int%26)+97)::"char" AS status
  FROM generate_series(1,50e6) AS gs(x);

CREATE INDEX ON messages (conversation_id , status);

ANALYZE messages;

From there, the only modification I made was to change your placeholder to 'a'.. IE,

AND "messages"."status" = $1;

to this,

AND "messages"."status" = 'a';

You can see the query plan here, the very same.

    QUERY PLAN                                                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=14.05..1734.48 rows=955000 width=4) (actual time=0.755..6.384 rows=31 loops=1)
   ->  HashAggregate  (cost=13.49..15.49 rows=200 width=4) (actual time=0.689..1.007 rows=899 loops=1)
         Group Key: "*VALUES*".column1
         ->  Values Scan on "*VALUES*"  (cost=0.00..11.24 rows=899 width=4) (actual time=0.002..0.282 rows=899 loops=1)
   ->  Index Only Scan using messages_conversation_id_status_idx on messages  (cost=0.56..8.58 rows=1 width=4) (actual time=0.006..0.006 rows=0 loops=899)
         Index Cond: ((conversation_id = "*VALUES*".column1) AND (status = 'a'::"char"))
         Heap Fetches: 31
 Planning time: 1.197 ms
 Execution time: 6.463 ms
(9 rows)

My assumption is that you either

1. have lots of dead rows, or a badly maintained index.
2. have a taxed out CPU, or taxed out ram.

For reference, my whole index is 1071 MB which fits into memory. If you can't fit it into memory you may be slightly slower but even if you have to page the index you can not account for that kind of slow down unless you have major IO bottlenecks -- it's only 1 GB.

Solution

Try VACUUM FULL messages.

Alternative plan

As I suggested in the comments too rewriting to an IN statement provides a slightly faster plan. If that saves you here, I think it's more luck though. I think you've got other problems.

    QUERY PLAN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using messages_conversation_id_status_idx on messages  (cost=0.56..4170.53 rows=36 width=4) (actual time=0.252..4.503 rows=31 loops=1)
   Index Cond: ((conversation_id = ANY ('{15934630,15934629,15388237,15697209,15603874,14751993,15890943,15880199,15879443,15879306,15876070,15876042,15875493,15852879,15854076,15853094,15853066,15776120,15822505,15827053,15825771,15822703,15815065,15815064,15814905,15811289,15810939,15810612,15805284,15805228,15805153,15805134,15805116,15796019,15778680,15778072,15777807,12729195,15776464,15776346,15742637,15742453,15742430,15730704,15730680,15730657,15730328,15730269,14329627,15730067,15696423,15695231,15694267,15642766,15642613,15642185,15639928,15633679,15639041,15638589,15637484,15637159,15637004,15636666,15636512,15636105,15635907,15635904,15635865,15634535,15634353,15634051,15633950,15633729,15633718,15633717,15633700,15631640,15631488,15631381,15626302,15625106,15624485,15610936,15607494,15604215,15584367,15572160,15570679,15570676,15570206,12232522,14667668,13432845,15483195,15495098,15495074,15495021,15493690,14920768,15493127,15450633,15489768,15488477,15369921,15484085,15484012,15483592,15483013,15482860,15480941,14329487,15480225,15479749,15479620,15477145,13125614,15467384,15466078,15457849,15457537,15451960,15451916,15451514,15451246,15369933,15415313,15411874,15409115,15408841,15408800,15408759,15407783,15408436,15408415,15404173,15403209,15403005,15400413,15399503,15397889,15376730,15359143,15338970,15338895,15337117,15337086,15335616,15334923,15334919,14378778,15325036,15324988,15124191,15128102,15285947,15285191,15284414,15273629,15200349,15259769,15259551,15258768,15258713,15258596,15254160,15253166,15253050,15252986,15252967,15252841,15252812,15251559,15249675,15240491,15218039,15216899,15215945,15200163,15196650,15181907,15181842,15179024,15166390,15128122,15145083,15128208,15128013,15067802,15088189,15088144,15087957,15085479,15085366,15084528,15084405,14954163,15072062,15059628,15054129,15048453,15045099,15044923,15000883,15000026,14998606,14997946,14996351,14996173,14996027,14991481,14991227,14984719,14961598,14958006,14957439,14926195,14920672,14955456,14955116,13125522,14927203,14926218,14920835,14920467,14915928,14915788,14914655,14913930,14911082,14910637,14910605,14899513,14899428,14833333,14664544,13503831,14858618,14842848,14699540,14836180,14836022,14835944,14835701,14835581,14835443,14544730,14835196,14835122,14834435,14834224,14833501,14826879,14826763,14824599,14822811,14822516,14737945,14703402,14551870,14732063,14731876,14392495,14664755,14664685,14664180,14664089,13320381,14586124,14572448,14547665,13891755,14549805,14532398,14544136,14545391,14545608,14536433,14383187,14391606,14502029,14502023,14501947,14493390,14493301,14493133,14493106,14492417,14491811,14483838,14478737,14451326,14422841,14422735,14382190,14396364,14385796,14095371,14340527,14340348,14340219,14340112,14339719,14339637,14339260,14329885,14338519,14338422,14337829,14337815,14330749,14329975,14329862,14255005,14290960,14290061,14289829,14267843,14260179,14259717,14259150,14254891,14254742,14250150,14246119,14170540,14169335,14153092,14127653,14095396,14095250,14084943,14084820,14084632,14002977,13971264,13924115,13962418,13946815,13885515,13938702,13930166,13924001,12868949,13857244,13854344,13851229,13850583,13850266,13850242,13848473,13846377,13846290,13845519,13844800,13844515,13841217,13841116,13818979,13812047,13745025,13771881,13730839,13730753,13755010,13745357,13616479,11115494,13771887,13772141,13767798,13767481,13766011,12955679,13764449,13764193,13763360,13763129,13762802,13730658,13754911,13750076,13747022,13605081,13731178,13731053,13730535,13729175,13679180,13672842,13619741,13616778,13596378,13594848,13573024,13572587,13503828,13569622,13566462,13539530,13538755,13538744,13538702,13537867,13463277,13462487,13462441,13400950,12150232,15406219,15405115,15404609,15404277,15403952,13400266,13141154,13395428,13395348,13394882,13392328,13059939,13319958,13319359,13318057,13316952,13304692,13302824,13297772,13296130,12464767,13243518,13227681,12729282,13202620,13169646,13169606,13168852,13164923,13164779,13164490,13161841,13125504,12949551,12949307,12948032,12947962,12947961,12946338,12916871,12944652,12941995,12929827,12928444,12928163,12927973,12925595,12923666,12913373,12883972,12883936,12880086,12855282,12878088,12875454,12869400,12857036,12854557,12850866,12848871,12847938,12836655,12812434,12811888,12811651,12811473,12808640,12808419,12805810,12804053,12803487,12803469,12803267,12803210,12803195,12803123,12800264,12800215,12790740,12790008,12770772,12768071,12737401,12730336,12728839,12728891,12728847,12727378,12727033,12706859,12534533,12073350,12667092,12667262,12667229,12593195,12581381,12565104,12138402,12547076,12546920,12446448,12367921,12536222,12534934,12536069,12464463,12518023,12512795,12442622,12511810,12207236,12501848,12501760,12500739,12500673,12497218,12483284,12380519,12466163,12466131,12464768,12464678,12464492,12462413,12446538,12446446,12371253,12073620,12413051,12375585,12373154,12373103,11806939,12371331,12369821,12368064,12366314,12366212,12366004,12345825,12304641,12304078,12302783,12301802,12300752,12300520,12298851,12298856,12298797,12233342,12233068,12231183,12231718,12151550,12229799,12208112,12202481,14493237,14456540,14430533,14420452,14395868,12185055,12153267,12151935,12151661,12150624,12147132,12147087,12143727,12143492,12142184,12138967,12138657,12133663,12035312,12111365,12083546,12109596,12083223,12103250,12083378,12080701,12075888,12075289,12075241,12073258,12073208,12031591,11585564,12011010,12005374,12005338,12004465,12003223,12003295,11996266,11996147,11987535,11985077,11982299,11978407,11978342,11977292,11976108,11066836,11946374,11946031,11945634,11944404,11944169,11942606,11942489,11942305,11905587,11896253,11887108,11871238,11873035,11871510,11868219,11867127,11862701,11809112,11855806,11852184,11852175,11795125,11841765,11841520,11840812,11831682,11836044,11836159,11809581,11809137,11808423,11808310,11807173,11806578,11803644,11800350,11799318,11794270,11793982,11793046,11385987,11784903,11773013,11773007,11771639,11762317,11736124,11736101,11736082,11736017,11735789,11735146,11732627,11729770,11729741,11725598,11718321,11717807,11717220,11716867,11715185,11427784,11662425,11372661,11615757,11557096,11587776,11587619,11586873,11586834,11586647,11586326,11585973,11585383,11585176,11558812,11558528,11557459,11557335,11548694,11519450,11519140,11518994,11516933,11504170,11503384,11501616,11489039,11483558,11470810,11458873,11458281,11458188,11457353,11455530,11454908,11450763,11450270,11450265,11443773,11441628,11441278,11434994,11429437,11428812,11420895,11419688,13105977,13105336,13105335,13100834,13098876,13092420,13092289,13090441,13074242,12805690,13044996,13060085,13050326,13027069,13026682,13024915,13020903,13020628,13020503,13017760,13016023,13012472,12926880,12761218,12970924,12955914,12955238,12949617,11419574,11408296,11392577,11390568,11389397,11386728,11372589,11382045,11381216,11381166,11377944,11377730,11377675,11375338,11374411,11372780,11372764,11364843,11364687,11363832,11363687,11219899,11224152,11228170,11230543,11230421,11235524,11237628,11039570,11250102,11250007,11249941,11250039,11250990,11252859,11252698,11255942,11258274,11259964,11260158,11261068,11261997,11263141,11263374,11038946,11040171,11040303,11040368,11040819,11040635,11040794,11041140,11041119,11041169,11041261,11041597,11041840,11041919,11042238,11044648,11049744,11289961,11296758,11040310,11065953,11040530,11066176,11066475,11066616,11066687,11066968,11067656,11068015,11068296,11067117,11068502,11073105,11072974,11066323,11073725,11074181,11073887,11075345,11076177,11078964,11079912,11084928,11087778,11039361,11089084,11299320,11036144,11093741,11098103,11295667,11106717,11106827,11109834,11110136,11110930,11322598,11111280,11322605,11041358,11111804,11112613,11112565,11326319,11113070,11326484,11326366,11326619,11326643,11326666,11327048,11113786,11329459,11332130,11333713,11332441,11333003,11333272,11334579,11336031,11335364,11336467,11336545,11128981,11136640,11138821,11139903,11151937,11112995,11152470,11162384,11170785,11174996,11175241,11174976,11176703,11176552,11176966,11177172,11067092,11209385,11209705,11210160,11211825}'::integer[])) AND (status = 'a'::"char"))
   Heap Fetches: 31
 Planning time: 1.175 ms
 Execution time: 4.879 ms
(5 rows)