ERROR: could not open relation with OID

We are trying to perform a 'reindex database' and it will fail at
varying points with a message like:
ERROR: could not open relation with OID 587495058
or
ERROR: could not open relation with OID 587603875

When we queried pg_class we got no rows returned:
select oid,* from pg_class where oid in (587603875, 587495058);
oid | relname | relnamespace | reltype | relowner | relam | relfilenode
| reltablespace | relpages | reltuples | reltoastrelid | reltoastidxid |
relhasindex | relisshared | relkind | relnatts | relchecks | reltriggers
| relukeys | relfkeys | relrefs | relhasoids | relhaspkey | relhasrules
| relhassubclass | relacl
-----+---------+--------------+---------+----------+-------+------------
-+---------------+----------+-----------+---------------+---------------
+-------------+-------------+---------+----------+-----------+----------
---+----------+----------+---------+------------+------------+----------
---+----------------+--------
(0 rows)

select oid,* from pg_class where oid>587603875;
oid | relname | relnamespace | reltype |
relowner | relam | relfilenode | reltablespace | relpages | reltuples |
reltoastrelid | reltoastidxid | relhasindex | relisshared | relkind |
relnatts | relchecks | reltriggers | relukeys | relfkeys | relrefs |
relhasoids | relhaspkey | relhasrules | relhassubclass | relacl
-----------+------------------------------+--------------+-----------+--
--------+-------+-------------+---------------+----------+-----------+--
-------------+---------------+-------------+-------------+---------+----
------+-----------+-------------+----------+----------+---------+-------
-----+------------+-------------+----------------+--------
587656467 | reindex_audit_network_id_idx | 2200 | 0 |
10 | 403 | 587656467 | 0 | 2 | 65 |
0 | 0 | f | f | i | 1 |
0 | 0 | 0 | 0 | 0 | f | f
| f | f |
587656343 | reindex_audit | 2200 | 587656344 |
10 | 0 | 587656343 | 0 | 1 | 65 |
0 | 0 | t | f | r | 8 |
0 | 0 | 0 | 0 | 0 | f | f
| f | f |
587656468 | reindex_audit_audit_id_idx | 2200 | 0 |
10 | 403 | 587656468 | 0 | 2 | 65 |
0 | 0 | f | f | i | 1 |
0 | 0 | 0 | 0 | 0 | f | f
| f | f |
(3 rows)

There were no reindex processes running in pg_stat_activity and
stopping/restarting postgres did not clear up these entries.

What could be causing these errors?