¿Obtener un valor aleatorio de un rango en MS SQL?

DECLARE @t TABLE
(VALUE CHAR(3))

INSERT @t
VALUES
('000'),('002'),('005'),('190')


;WITH rnCTE
AS
(
    SELECT -1 + ROW_NUMBER() OVER (ORDER BY TYPE, number, name) AS rn
    FROM master.dbo.spt_values
)
SELECT RIGHT('000' + CAST( rn AS VARCHAR(11)),3)
FROM rnCTE
WHERE NOT EXISTS    (   SELECT 1 FROM @t 
                        WHERE VALUE = rn
                    )
AND rn < 1000

EDITAR

Esta consulta funciona generando la lista completa de posibles números a partir de una tabla del sistema (master.dbo.spt_values ) que se garantiza que contiene más de 1000 filas dentro del CTE rnCTE . -1 se agrega a ROW_NUMBER para que los valores comiencen en 0 en lugar de 1.

La consulta externa cero rellena los números para mostrar, devolviendo solo aquellos que no están en los datos de origen y son inferiores a 1000.