Ok... here's a test table with some huge gaps over a huge range of numbers along with some single row gaps. The code takes about 12 seconds to run on my 8 year old machine. Details are in the comments, as usual...

DROP TABLE #MyTest

GO

--===== Create and populate a 2,000,000 row test table.

-- This first SELECT creates a range of 1 to 1,000,000 unique numbers starting at 10,000,001

SELECT TOP 1000000

MyID = ISNULL(CAST(ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) + 10000000 AS BIGINT),0)

INTO #MyTest

FROM Master.sys.All_Columns ac1,

Master.sys.All_Columns ac2

-- This second SELECT creates a range of 1 to 1,000,000 unique numbers starting at 82,011,000,000,001

UNION ALL

SELECT TOP 1000000

MyID = ISNULL(CAST(ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) + 82011000000000 AS BIGINT),0)

FROM Master.sys.All_Columns ac1,

Master.sys.All_Columns ac2

--===== Create the quintessential Primary Key

-- Takes about 3 seconds to execute.

ALTER TABLE #MyTest

ADD PRIMARY KEY CLUSTERED (MyID)

--===== Delete some know rows to demo the gap detection code

-- This deletes 50 rows spaced 2000 apart in the given range

-- to demo small gaps

DELETE #MyTest

WHERE MyID BETWEEN 82011000400001 AND 82011000500000

AND MyID %2000 = 0

-- This deletes 100,000 rows in a given range to demo large gaps

DELETE #MyTest

WHERE MyID BETWEEN 82011000600001 AND 82011000700000

Here's the gap detection code I spoke of. It takes about 3 seconds to run on that same 8 year old machine. I'm thinking that because of the very large ranges of numbers that a Tally table just isn't going to cut it for stuff like this...

--===== Find the "gap ranges" --This takes 3 seconds on my 8 year old machine

-- Finds trailing edge of "islands" and then computes the gaps

-- This assumes that gaps include any whole number greater than 0

SELECT GapStart = (SELECT ISNULL(MAX(lo.MyID),0)+1

FROM #MyTest lo

WHERE lo.MyID < hi.MyID),

GapEnd = hi.MyID - 1

FROM #MyTest hi

WHERE hi.MyID NOT IN (SELECT MyID + 1 FROM #MyTest)