without index,select is slow,after adding index,dead lock occurs,please come into help me.

I have a table which is used to store and handle messages and I also have two stored procudure about it,one is GetBatchMessage another is UpdateMessage(you can see from the following schema).
the column DelvieryGroup has just 4 vales in the table,the column DelvierStauts has near 200 values,the DeliveryStatus,DeliveryGroup and ProcessFlag will be updated very frquently,so I have not created any index on them.But the GetBatchMessage is very slow,500 per second.I tried to add index on DeliveryType and
ChannelId which are stable during the whole process,but it has not promoted GetBatchMessage performance a lot.I try to add some index on DeliveryStatus,DeliveryType,ChannelId,
ProcessFlag,GetBatchMessage can get 5000 records/sec but dead lock might happen during GetBatchMessage and UpdateMessage, one locking it to select,another try to lock it to update the index.
Anybody please help me.

CREATE TABLE [dbo].[MobileMessage](
[MessageId] [uniqueidentifier] ROWGUIDCOL NOT NULL,
[ChannelId] [smallint] NULL,
[Message] [varbinary](max) NULL,
[DeliveryStatus] [smallint] NOT NULL,
[DeliveryGroup] [tinyint] NOT NULL,
[DeliveryType] [tinyint] NOT NULL,
[ProcessFlag] [bit] NOT NULL,
CONSTRAINT [PK_MobileMessage_MessageID] PRIMARY KEY CLUSTERED
(
[MessageId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)
)
GetBatchMessage:
BEGIN
UPDATE TOP (@BatchSize) MobileMessage
SET
LastUpdatedTime = @Time,
ProcessFlag=1
OUTPUT INSERTED.Message
WHERE
DeliveryStatus=@DeliveryStatus AND
DeliveryType=@DeliveryType AND
ChannelId=@ChannelId AND
ProcessFlag =0
END
UpdateMessage:
UPDATE
dbo.MobileMessage
SET
ChannelId = ISNULL(@ChannelId, ChannelId),
Message = ISNULL(@Message, Message),
DeliveryStatus=@DeliveryStatus,
DeliveryType=@DeliveryType,
DeliveryGroup=@DeliveryGroup,
ProcessFlag =0
WHERE
MessageId = @MessageId

following is the dead lock log
deadlock-list
2009-07-01 06:48:40.57 spid29s deadlock victim=processfebc8
2009-07-01 06:48:40.57 spid29s process-list
2009-07-01 06:48:40.57 spid29s process id=processfebc8 taskpriority=0 logused=0 waitresource=KEY: 7:72057594043367424 (6a02c503d067) waittime=2325 ownerId=14993 transactionname=UPDATE lasttranstarted=2009-07-01T06:48:32.527 XDES=0x8f3ba3b0 lockMode=U schedulerid=1 kpid=7428 status=suspended spid=146 sbid=0 ecid=0 priority=0 trancount=2 lastbatchstarted=2009-07-01T06:48:32.527 lastbatchcompleted=2009-07-01T06:48:32.527 clientapp=.Net SqlClient Data Provider hostname=SZMOBMDSTST04 hostpid=4712 loginname=PHXxiahu isolationlevel=read committed (2) xactid=14993 currentdb=7 lockTimeout=4294967295 clientoption1=538968096 clientoption2=128056
2009-07-01 06:48:40.57 spid29s executionStack
2009-07-01 06:48:40.57 spid29s frame procname=Mobile_SMS_1.dbo.GetMobileMessages line=45 stmtstart=3324 stmtend=3984 sqlhandle=0x030007005a33f607a5b66900399c00000100000000000000
2009-07-01 06:48:40.57 spid29s UPDATE TOP (@BatchSize) MobileMessage
2009-07-01 06:48:40.57 spid29s SET
2009-07-01 06:48:40.57 spid29s LastUpdatedTime = @Time,
2009-07-01 06:48:40.57 spid29s ProcessFlag=1
2009-07-01 06:48:40.57 spid29s OUTPUT INSERTED.Message
2009-07-01 06:48:40.57 spid29s WHERE
2009-07-01 06:48:40.57 spid29s DeliveryGroup=@DeliveryGroup AND
2009-07-01 06:48:40.57 spid29s ChannelId=@ChannelId AND
2009-07-01 06:48:40.57 spid29s ProcessFlag =0
2009-07-01 06:48:40.57 spid29s inputbuf
2009-07-01 06:48:40.57 spid29s Proc [Database Id = 7 Object Id = 133575514]
2009-07-01 06:48:40.57 spid29s process id=process3e8b4c8 taskpriority=0 logused=380 waitresource=KEY: 7:72057594043367424 (690224b58288) waittime=6045 ownerId=21264 transactionname=UPDATE lasttranstarted=2009-07-01T06:48:34.523 XDES=0x8f9e83b0 lockMode=X schedulerid=7 kpid=2088 status=suspended spid=77 sbid=0 ecid=0 priority=0 trancount=2 lastbatchstarted=2009-07-01T06:48:34.523 lastbatchcompleted=2009-07-01T06:48:34.523 clientapp=.Net SqlClient Data Provider hostname=SZMOBMDSTST01 hostpid=7256 loginname=PHXxiahu isolationlevel=read committed (2) xactid=21264 currentdb=7 lockTimeout=4294967295 clientoption1=538968096 clientoption2=128056
2009-07-01 06:48:40.57 spid29s executionStack
2009-07-01 06:48:40.57 spid29s frame procname=Mobile_SMS_1.dbo.UpdateMobileMessage line=22 stmtstart=1412 stmtend=2758 sqlhandle=0x0300070076a2250428dff800269c00000100000000000000
2009-07-01 06:48:40.57 spid29s UPDATE
2009-07-01 06:48:40.57 spid29s dbo.MobileMessage
2009-07-01 06:48:40.57 spid29s SET
2009-07-01 06:48:40.57 spid29s ChannelId = ISNULL(@ChannelId, ChannelId),
2009-07-01 06:48:40.57 spid29s Sender = ISNULL(@Sender, Sender),
2009-07-01 06:48:40.57 spid29s Receiver = ISNULL(@Receiver, Receiver),
2009-07-01 06:48:40.57 spid29s Message = ISNULL(@Message, Message),
2009-07-01 06:48:40.57 spid29s SmsApplicationId = ISNULL(@SmsApplicationId, SmsApplicationId),
2009-07-01 06:48:40.57 spid29s ExpiresAt = ISNULL(@ExpiresAt, ExpiresAt),
2009-07-01 06:48:40.57 spid29s LastUpdatedTime = GETUTCDATE(),
2009-07-01 06:48:40.57 spid29s DeliveryStatus=@DeliveryStatus,
2009-07-01 06:48:40.57 spid29s DeliveryType=@DeliveryType,
2009-07-01 06:48:40.57 spid29s Version=@Version,
2009-07-01 06:48:40.57 spid29s DeliveryGroup=@DeliveryGroup,
2009-07-01 06:48:40.57 spid29s ProcessFlag =0
2009-07-01 06:48:40.57 spid29s WHERE
2009-07-01 06:48:40.57 spid29s MessageId = @MessageId
2009-07-01 06:48:40.57 spid29s inputbuf

If this is a multi threaded application, use the READPAST table hint.
Excerpt from BOL: Use the READPAST table hint in UPDATE and DELETE statements if your scenario allows for multiple applications to perform a destructive read from one table. This prevents locking issues that can come up if another application is already reading the first qualifying record in the table.

If not right this minute, you will soon need an index on your table. You have already identified the index that will improve your performance, now all you need to do is to turn it into a COVERING INDEX so that you preclude the deadlocks. I would also make it a nonclustered index, just to minimize the performance issues involved with a lot of inserts and updates.
If you know what a COVERING INDEX is, you won't need to read the rest of this message; however, if you don't know what one is, then keep reading. ;-)
A COVERING INDEX is an index that has more columns in it than are strictly needed for the index and all of the columns that will be needed by the query. You don't mention whether this is SS2000, SS2005, or SS2008. In SS2000, you have to include the additional columns in the index specification. In SS2005 and SS2008, you can add the additional columns in the INCLUDE columns. (Both approaches function pretty much the same in one sense and you can simply add the columns to the index specification in SS2005/2008. ;-)