SELECT TOP 1 from a very large table on an index column is very slow, but not with reverse order ("desc")
The Clustered Index Scan shows 423,723 logical reads to return the first row, taking 1926 ms:

This seems rather a lot to locate the first row in index order.
Most likely your ghost cleanup task is running a long way behind, or has stopped. You should check the ghost_record_count for the clustered index in sys.dm_db_index_physical_stats and monitor changes over time.
The ordered scan from the end of the index that is seeing constant delete activity has to scan over an awful lot of ghosted records before it finds the first 'alive' row to return. This explains the extra logical reads. A seek down the b-tree to the lowest value of the index will encounter much fewer ghosted records.
Another performance-affecting factor is that the scan itself becomes responsible for removing the ghost records as mentioned in Inside the Storage Engine: Ghost cleanup in depth by Paul Randal.
You should check that trace flag 661 (disable ghost cleanup) is not active.
Solutions

You may find that running sp_clean_db_free_space provides relief.
Changing the process that deletes rows from that end of the index to use a PAGLOCK hint would enable ghost cleanup on the spot, which could well solve the problem as well.

If the ghost cleanup process has stopped completely, the most effective solution is normally to restart the SQL Server instance. You should also ensure that the SQL Server is running one of the latest Cumulative Updates. There have been many ghost cleanup bugs over the years.
In your specific case:

It turned out the problem was caused by another test database on the same server. That test database was restored with &quot;data loss&quot;, and is corrupt. Surprisingly, the ghost cleanup process apparently was stuck in that database. Once we deleted that corrupted database from SMSS, the problem resolved by itself (took a long time and might have caused DB to lockup for a short while).