Tengo la siguiente tabla que contiene valores leídos cada 15 minutos desde varios dispositivos diferentes:

ID   DeviceID   Date                    Value
----------------------------------------------
1    3          24.08.2011 00:00:00     0.51
2    3          24.08.2011 00:15:00     2.9
3    3          24.08.2011 00:30:00     0
4    3          24.08.2011 00:45:00     7.1
5    3          24.08.2011 01:00:00     1.05
6    3          24.08.2011 03:15:00     3.8

Me gustaría encontrar todos los huecos en la tabla para cada dispositivo, donde no hay entradas, para un mes determinado. Para la tabla de arriba, el resultado debería ser algo como esto:

DeviceID    StartDate               EndDate
-------------------------------------------------------
3           24.08.2011 01:00:00     24.08.2011 03:15:00

La tabla tiene aproximadamente 35000 dispositivos y 100 millones de entradas.

Esto es lo que intenté; Es bastante lento, pero devuelve lo que necesito. Sin embargo, además de su velocidad, hay otro problema: solo encuentra intervalos faltantes hasta la última entrada de un dispositivo en el mes dado; después de eso, se ignorará, por lo que es posible perder un intervalo adicional de valores perdidos.

SELECT
    t2.Date AS StartDate
    , t1.Date AS EndDate
FROM
    TestTable t1
    INNER JOIN TestTable t2 ON t1.DeviceID = t2.DeviceID
WHERE
    (t2.Date = (SELECT MAX(Date) FROM TestTable t3 WHERE t3.Date < t1.Date AND t3.DeviceID = t1.DeviceID)
        AND DATEDIFF(MINUTE, t2.Date, t1.Date) > 15)
    AND t1.DeviceID = @id
    AND DATEPART(YEAR, t1.Date) = @year AND DATEPART(MONTH, t1.Date) = @month