Query records that chain together based on date gaps
The following solution (SQL Fiddle) uses the SQL Server 2012LAST_VALUE function:

SELECT
    MaxDiff.ID,
    MaxDiff.Arrival,
    MaxDiff.Departure
FROM 
(
    -- Maximum difference encountered so far
    SELECT *,
        MaxDiff = LAST_VALUE(Diff.Diff)  OVER (
            ORDER BY Diff.Departure DESC 
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
    FROM 
    (
        -- Difference between departure and prior arrival
        SELECT *,
            Diff = 
                ISNULL(DATEDIFF(DAY, r.Departure,
                        LAST_VALUE(r.Arrival) OVER (
                            ORDER BY r.Departure DESC 
                            ROWS BETWEEN 1 PRECEDING AND 1 PRECEDING)), 0)
        FROM dbo.Records AS r
    ) AS Diff
) AS MaxDiff
WHERE
    MaxDiff.MaxDiff &lt;= 30
ORDER BY
    MaxDiff.Departure DESC;


Results:

╔════╦════════════╦════════════╗
║ ID ║  Arrival   ║ Departure  ║
╠════╬════════════╬════════════╣
║  4 ║ 2009-07-19 ║ 2009-07-24 ║
║  3 ║ 2009-06-11 ║ 2009-07-01 ║
║  2 ║ 2009-04-27 ║ 2009-05-21 ║
║  1 ║ 2009-04-19 ║ 2009-04-28 ║
╚════╩════════════╩════════════╝


Execution plan: