Slow query even with aggressive auto analyze

This query http://pgsql.privatepaste.com/359bed8e9e gets executed every
500 ms and normally completes really quickly
http://explain.depesz.com/s/poVQ, but the more job_batches table
(http://pgsql.privatepaste.com/eaf6d63fd2) gets used, the slower this
query gets, to the point where it takes minutes to execute
http://explain.depesz.com/s/rDJ.

Analyzing job_batches table resolves the issue immediately. This table
gets about a thousand new records an hour that are also updated three
times as the status changes. No deletion is occurring.

I've tried changing autovacuum_analyze_scale_factor as well as setting
job_batches table to auto analyze every 500 changes (by setting scale
factor to 0 and threshold to 500), but I still keep running into that
issue, sometimes minutes after the table was analyzed.

I checked pg_locks to see if anything had granted=false, but that
doesn't seem to be the case.

This issue is occurring on two separate instances 9.0.4 and 9.1.4 - both
have nearly identical settings, just run on a different hardware.

Config changes http://pgsql.privatepaste.com/8acfb9d136

Any ideas what is going wrong here?