> Nobody ever deleted anything from this table. Since it was created, this has been a write-only table.
does write-only include updates? that would create the dead rows tom is referring to.
> I believe it is not actually using the index, because reading a single (random?) entry from an index should not run for >10 minutes.
it is using the index. You can disable it, and see how long your query takes ("set enable_indexonlyscan = off", optionally enable_indexscan too), chances are it will take even longer. If somehow it does not, by luck, then you no vacuum has run for a while, for some reason (perhaps canceled due to frequent table activity?). That too you can check.