SQL2k5 introduced APPLY so you're ok with it in your query. Here's a version which uses a 2k5 compliant row generator:

;WITH Tens (n) AS (

SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL

SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0

),

RowGenerator AS (

SELECT n = ROW_NUMBER() OVER(ORDER BY (SELECT NULL))

FROM Tens a CROSS JOIN Tens b CROSS JOIN Tens c CROSS JOIN Tens d CROSS JOIN Tens e

)

SELECT

location_id,

unoccupied_start_dt = CASE WHEN seq = 1 THEN NULL ELSE unoccupied_start_dt END,

unoccupied_end_dt = CASE WHEN seq = [Rows] THEN NULL ELSE unoccupied_end_dt END

FROM (

SELECT

location_id,

unoccupied_start_dt = MIN(Timespot),

unoccupied_end_dt = MAX(Timespot),

seq = ROW_NUMBER() OVER(PARTITION BY location_id ORDER BY TimeGroup),

[Rows] = COUNT(*) OVER(PARTITION BY location_id)

FROM (

SELECT

s.location_id, s.MIN_start_dt, s.MAX_end_dt,

x.Timespot,

TimeGroup = DATEADD(minute,1-ROW_NUMBER() OVER(PARTITION BY s.location_id ORDER BY x.Timespot), x.Timespot)

FROM (SELECT location_id, MIN_start_dt = MIN(start_dt), MAX_end_dt = MAX(end_dt) FROM #stays GROUP BY location_id) s

CROSS APPLY (

SELECT TOP (DATEDIFF(minute,s.MIN_start_dt,s.MAX_end_dt)+3)

TimeSpot = DATEADD(minute,n-2,s.MIN_start_dt)

FROM RowGenerator

) x

WHERE NOT EXISTS (SELECT 1 FROM #stays l WHERE l.location_id = s.location_id

AND x.Timespot BETWEEN l.start_dt AND l.end_dt)

) d

GROUP BY location_id, TimeGroup

) o