Paged query against timestamp populated by trigger missing items
I think you found the main culprit alright. There are more ways to miss rows with this setup. Consider D3 I added to your time diagram:


D1 |st1....................|
D2       |st2......|
D3          |st3......|
R                |.......|
                   ^ -- read query starts here


Transaction D3 starts after D2, but since it's not committed when your read query in transaction R starts, it is invisible as well. It will be included in the next page, but it may still be confusing that it's missing this time. That's how the default transaction isolation level Read Committed is defined. You seem to be aware of it, but for the general public:


  When a transaction uses this isolation level, a SELECT query (without
  a FOR UPDATE/SHARE clause) sees only data committed before the query
  began; it never sees either uncommitted data or changes committed
  during query execution by concurrent transactions. In effect, a SELECT
  query sees a snapshot of the database as of the instant the query
  begins to run.


There is more. Read the manual.



With concurrent access to the DB, various conflicts might stall a DELETE query - which will patiently wait until it can get an exclusive lock on the rows to delete. 10 minutes of missed rows would indicate a (possibly unrelated) problem, I agree with your suspicion. Transactions that remain "idle in transaction" are prime suspects. To diagnose, look for log long running statements or transactions. Some pointers:


Set log_min_duration_statement in postgresql.conf.
Some basics on Logging Difficult Queries in the Postgres Wiki.
The statistics view pg_stat_activity. Related:


Postgres - estimate end time for a long update

check_postgres provides helpful tools.
Related blog.


Database design

You seem to be using data type timestamp. Your INSERT with statement_timestamp() AT TIME ZONE 'UTC' should work correctly for your purpose, but you shouldn't rely on INSERT statements to get this right. Rather move the logic to the table itself. Use the data type timestamptz (timestamp with time zone) for tombstone.delete_timestamp to begin with. This rules out any discrepancies with time zones or DST (daylight saving time). Details:


Ignoring timezones altogether in Rails and PostgreSQL


Also don't rely on the INSERT statement to provide the correct time. Put the logic in the column default (or even in a trigger BEFORE INSERT to overwrite any provided timestamp).

CREATE TABLE tombstone (
  id int NOT NULL PRIMARY KEY  -- assuming PK
, delete_timestamp timestamptz DEFAULT statement_timestamp()
);


Since timestamps are not visible until the transaction is committed anyway, the cheaper current_timestamp (transaction timestamp) may be just as useful as statement_timestamp() - depends on unknown details.

The simpler INSERT statement in the trigger to go with the above:

INSERT INTO tombstone (id) VALUES (OLD.id);


Query

Your current SELECT query can be faster comparing row values, which is also index-backed in Postgres:

SELECT id, delete_timestamp
FROM   tombstone
WHERE  (delete_timestamp, id) &gt; (@sinceUTC, @id)
ORDER  BY delete_timestamp, id
LIMIT  @count;


Details:


Optimize query with OFFSET on large table


Secure alternative

All this aside, timestamps are just not completely reliable for queuing or paging in a multi-user environment. If you need it to be completely reliable, consider a different approach: Lock unread rows before retrieving and mark them as read. The new FOR UPDATE SKIP LOCKED in Postgres 9.5 may prove useful for this:


Postgres UPDATE ... LIMIT 1


Or, if the reading is done by a single user, you don't need locks. Just mark rows you have read. A partial index for unmarked rows makes reading fast.

Upgrade to current Postgres

Postgres 9.2 is getting old. Upgrading to the current version might help for various reasons.