Work queue with complex select and long processing: Ensuring concurrency
You mentioned you could not use 'locking by deletion' because the row must stay in the table. The code example below does use it, but only after creating a global queue first and populating it. It then uses the 'locking by deletion' for the ##Queue table rather than the table you're working with.

USE master
GO

    -- 1. Create a Stored Procedure that creates the Queue and populates it based on the criteria you have.
    --      (this doesn't have to be a Stored Procedure, but can also be run via some other method to populate the queue.)
    --      (also update 'DatabaseName.SchemaName.the_table' to be the name of your table.)

    IF EXISTS (SELECT * FROM master.dbo.sysobjects o WHERE o.xtype IN ('P') AND o.id = object_id('master.dbo.CreateQueue'))
    DROP PROC CreateQueue
    GO

    CREATE PROCEDURE dbo.CreateQueue
    AS
    BEGIN
        IF OBJECT_ID('Tempdb.dbo.##Queue') IS NOT NULL
        DROP TABLE ##Queue

        SELECT * INTO ##Queue FROM DatabaseName.SchemaName.the_table WHERE &lt;replace with your criteria&gt; 
    END
    GO

    -- 2. Execute the SP above or use the code some other way to create the ##Queue

    -- 3. Copy the code below and run it via multiple processes if you like, as there should not be concurrency issues.
    WHILE 1 = 1
        BEGIN
            DELETE TOP ( 1 )
                    ##Queue WITH ( READPAST )
            OUTPUT  Deleted.*
                    INTO #RowToProcess
            IF @@ROWCOUNT &gt; 0 
                BEGIN
                    --Place logic here to work with the row...
                    DELETE  FROM #RowToProcess
                END
            ELSE
                BREAK
        END