Efficient way to fetch records since a given criteria

I'm trying to implement a logic where the user can say give me n records since a given id#. E.g.

SELECT TOP (100) col1, col2, ... colN 
FROM Table1
WHERE ID > @id
ORDER BY ID

Performance is the biggest issue here, especially when you get into nested loops for complex joins. I've looked at the new OFFSET-FETCH feature in SQL Server 2012 but they require you to specify a number rather than a WHERE clause. I wouldn't know the offset unless I count num rows beforehand.

Is there an alternate way to do this efficiently in SQL Server (2008 R2 and above)?

Update: Complete SQL as generated by EF Code first

-- Region Parameters
DECLARE @p__linq__0 BigInt = 60375518904121
DECLARE @p__linq__1 BigInt = 60375518904121
-- EndRegion
SELECT 
[Project3].[Id] AS [Id], 
[Project3].[C2] AS [C1], 
[Project3].[C1] AS [C2], 
[Project3].[C3] AS [C3] 
FROM ( SELECT 
    [Limit1].[Id] AS [Id], 
    [Limit1].[C1] AS [C1], 
    [Limit1].[C2] AS [C2],
    [Limit1].[TmId] AS [TmId], 
    CASE WHEN ([Extent4].[TmId] IS NULL) THEN CAST(NULL AS int) ELSE 1 END AS [C3]
    FROM   (SELECT TOP (100) [Project2].[Id] AS [Id], [Project2].[TmId] AS [TmId], [Project2].[C1] AS [C1], [Project2].[C2] AS [C2]
        FROM ( SELECT 
            [Extent1].[Id] AS [Id], 
            [Extent2].[TmId] AS [TmId], 
            CASE WHEN ([Extent2].[TmId] IS NULL) THEN CAST(NULL AS int) ELSE 1 END AS [C1], 
            1 AS [C2]
            FROM  [dbo].[TextMessages] AS [Extent1]
            LEFT OUTER JOIN [dbo].[Tms] AS [Extent2] ON [Extent1].[Id] = [Extent2].[TmId]
            WHERE ( EXISTS (SELECT 
                1 AS [C1]
                FROM [dbo].[Tmr] AS [Extent3]
                WHERE ([Extent1].[Id] = [Extent3].[TmId]) AND ([Extent3].[IsDel] = 1) AND ([Extent3].[UserId] = @p__linq__0)
            )) OR ([Extent1].[CreatedBy_Id] = @p__linq__1)
        )  AS [Project2]
        ORDER BY [Project2].[Id] DESC ) AS [Limit1]
    LEFT OUTER JOIN [dbo].[Tmr] AS [Extent4] ON [Limit1].[Id] = [Extent4].[TmId]
)  AS [Project3]
ORDER BY [Project3].[Id] DESC, [Project3].[TmId] ASC, [Project3].[C3] ASC

Update: The real bottleneck turned out to be network latency caused by EC2 servers.