INSERT/UPDATE statements sometimes choosing not to use PK index?

I have a relatively simple data load script, which upserts (UPDATE existing
rows, INSERT new rows), which should be supported by the primary key index,
the only index on this table:

UPDATE destination SET ... FROM staging WHERE staging.pk =
destination.pk;
INSERT INTO destination SELECT ... FROM staging WHERE NOT EXISTS(SELECT
* FROM destination WHERE pk = staging.pk);

In most cases, EXPLAIN and runtime tell me the index is utilized. However,
sometime on back to back runs (5 minute intervals) the runtime explodes and
EXPLAIN shows me that the PK index is not used, as both the staging table
and destination table a sequentially scanned. The source data maintains the
same pattern, and this load job is the only write activity in this
particular database.

A left anti-join in the above pseudo-query explains the same, and seems to
make the problem occur more frequently.

What could cause PostgreSQL (9.1) to stop using an index in a case like
this, when it normally and expectedly uses it?