Need A Fast Queue Using A Table

I am trying to implement a very fast queue using SQL Server.

The queue table will contain tens of millions of records.

The problem I have is the more records completed, the the slower it
gets. I don't want to remove data from the queue because I use the
same table to store results. The queue handles concurrent requests.

The status field will contain the following values:
0 = Waiting
1 = Started
2 = Finished

Any help would be greatly appreciated.

Here is a simplified script to demonstrate what has been done.

CREATE TABLE [dbo].[Queue] (
[ID] [int] IDENTITY (1, 1) NOT NULL ,
[JobID] [int] NOT NULL ,
[Status] [tinyint] NOT NULL
) ON [PRIMARY]
GO

CREATE INDEX [Status] ON [dbo].[Queue]([Status]) ON [PRIMARY]
GO

CREATE PROCEDURE dbo.NextItem
@JobID integer,
@ID integer output
AS
SELECT TOP 1 @ID = [ID]
FROM Queue WITH (READPAST, XLOCK)
WHERE (Status = 0) AND (JobID = @JobID)
RETURN
GO