[Erwin]

Is it a HSTORE column with GIN index? The default "FASTUPDATE=ON" option will delay updates to the index until vacuum time, but if you don't vacuum soon enough suddenly it can decide it should sequentially scan instead of reading through the delayed updates.

This is behaviour I've seen on 9.x on the Aurora variant; for that the solution was to use the FASTUPDATE=OFF index storage option. You can see the delayed tuples by using "pgstatginindex" function.

Using some of the extra options of EXPLAIN (ANALYZE, BUFFERS, COSTS) might give more hints.

If not HSTORE/GIN, then it could be that the analyzer, after some auto-analyze of the table things that what you are asking for will match a significant number of the rows in the table. So there's no point in random seeking through an index because it thinks it needs to read e.g. 50% of the table anyway, so it might just as well not use the index.