Implementing Message Queue In SQL Server 2000

I am implementing a message queue system in SQL Server 2000. My queue table looks something like this:

[MessageId] [uniqueidentifier] NOT NULL,
[MessageType] [uniqueidentifier] NOT NULL,
[Status] [tinyint] NOT NULL,
[SubmittedTime] [datetime] NOT NULL,
[StartTime] [datetime] NOT NULL,
[DispatchedTime] [datetime] NULL,
[CompletedTime] [datetime] NULL,
[MessageData] [image] NULL

This is how I retrieve the next message for processing:

SELECT TOP 1 *
FROM [Queue].[MessageQueue] WITH (ROWLOCK, UPDLOCK, READPAST)
WHERE [StartTime]=@pStartTime AND [MessageType]=@pMessageType AND [Status]=@pStatus
ORDER BY [StartTime]

and mark it as being processed:

UPDATE [Queue].[MessageQueue] SET [Status]=1 WHERE [MessageId]=@pMessageId

After message has been processed I delete it from the queue:

DELETE FROM [Queue].[MessageQueue] WHERE [MessageId]=@pMessageId

All database accesses are transactional with default READ COMMITTED. The problems start when there are a few concurrent accesses: I get deadlocks when retrieving next message. If I do not delete message after processing then there is no deadlock. But this is not what I need.

I played with different isolation levels and locking hints and was able to avoid deadlock using TABLOCKX:

SELECT .... FROM [Queue].[MessageQueue] WITH (TABLOCKX)

But in this case you cannot concurrently retrieve messages which was my goal from the beginning. How do I achieve this?

Thank you,
Alex