Sql-server – LOCK error after creating a clustered index

I would be confident you have corruption. Sounds like at least one corrupt data page. What does the contents of msdb.dbo.suspect_pages look like? Refer to http://msdn.microsoft.com/en-us/library/ms191301(v=sql.105).aspx for parsing some of that info.

You can use the OUTPUT clause to see if the chain of events should be "fired":

My test-bed:

CREATE TABLE dbo.OrderedChainFlag
(
    IsChainFired BIT NOT NULL
        CONSTRAINT DF_OrderedChainFlag_IsChainFired
        DEFAULT ((0))
    , OrderID INT NOT NULL
);

CREATE INDEX IX_OrderedChainFlag_Firing
ON dbo.OrderedChainFlag(OrderID, IsChainFired);

GO

INSERT INTO dbo.OrderedChainFlag (OrderID)
VALUES (123456);

Run this to see the output:

UPDATE OrderedChainFlag 
SET IsChainFired = 1 
OUTPUT inserted.IsChainFired, inserted.OrderID
WHERE OrderId = 123456 
    and IsChainFired = 0;

Use a DataReader to read the results of the UPDATE statement; if a row is returned by .Read() you know the table was updated, and effectively, you can run the chain of events.

Running the UPDATE statement above will only ever provide output if it actually updated the IsChainFired column to 1. You can prove that by running the update statement twice. The first one shows output, the second one does not.

Since this one statement is atomic, one-and-only-one update will succeed, without affecting lock escalation, assuming you have a good index on OrderId and IsChainFired, and that index is configured WITH (ALLOW_ROW_LOCKS = ON).

Second option, which is a slight variation on the above, would be to not specify the next OrderID to be processed; instead simply select the next one that has IsChainFired = 0:

CREATE INDEX IX_OrderedChainFlag_IsFired
ON dbo.OrderedChainFlag(IsChainFired);

UPDATE TOP(1) OrderedChainFlag 
SET IsChainFired = 1 
OUTPUT inserted.IsChainFired, inserted.OrderID
WHERE IsChainFired = 0;

The UPDATE statement in this case returns the OrderID for a single row directly from the IX_OrderedChainFlag_IsFired index.

I inserted over 750,000 rows into the OrderedChainFlag table in my test-bed, and ran the above UPDATE TOP(1) statement, with the index I mention in place, and got the following plan:

A (arguable) bonus here is you could potentially return more than TOP(1) rows for processing, perhaps using multiple threads in your Web Service.

You should probably also read this question, along with the excellent answers on concurrency.