Add a 'Being Processed' Flag to each record, which is set in an 'atomic' way.

There have been several questions and many answers here on SO, quite similiar to this:

How do I lock certain SQL rows while running a process on them?

Queues against Tables in messaging systems

What’s the best way of implementing a messaging queue table in mysql

Posting Message to MSMQ from SQL Server

this is quite an old question and probably the author's problem is long gone now but there's a little SQL trick that solves it and can be useful to others: the 'readpast' hint. With readpast sql select will skip locked rows in a query. What you want is to grab first unlocked row and immediately lock it so no one else will get it:

select top 1 * 
from messages with(readpast, updlock) 
order by id

This will select and lock the first free message in the table and so no one else will be able to modify it. Actually I'm using the same approach in SQL-based message bus: https://code.google.com/p/nginn-messagebus/ and it works very smoothly (sometimes faster than MSMQ)

Take a look at SQL Server Service Broker , it is designed for this kind of problem.

If you need a queue, use a queue.

Add a "grabbed" column to the messages table. Everyone can try to grab a row with a single SQL statement:

UPDATE m
SET grabbed = 1
FROM messages m
WHERE id = @myid
and grabbed = 0

After this, if @@ROWCOUNT is 1, the row is yours. Otherwise, somebody else grabbed the row before you.

SQL Server Broker or MSMQ or MQSeries introduce massive complexity and maintenance overhead. Be sure the operations guy that's receiving your stuff agrees before you start using it.