Make index work on join to table variable
Assuming your variables are always NOT NULL

WHERE  ( ReceiveDateTime &lt; @DocOldestTreshold
          OR ( ReceiveDateTime &lt; @DocNewestTreshold
               AND ReceiveDateTime &lt; t.Treshold ) ) 


Is equivalent to

WHERE  ReceiveDateTime &lt; @DocOldestTreshold
        OR ReceiveDateTime &lt; LEAST(@DocNewestTreshold, t.Treshold) 


Which is equivalent to

WHERE  ReceiveDateTime &lt; GREATEST(@DocOldestTreshold, LEAST(@DocNewestTreshold, t.Treshold)) 


So if you have this index

CREATE INDEX ix
  ON [DocumentInfo](StatusId, [ReceiveDateTime])


And the following query

SELECT di.DocumentId
FROM   @Tresholds T
       CROSS APPLY (SELECT IIF(@DocNewestTreshold &lt; t.Treshold, @DocNewestTreshold, t.Treshold)) CA1(Least)
       CROSS APPLY (SELECT IIF(@DocOldestTreshold &gt; CA1.Least, @DocOldestTreshold, CA1.Least)) CA2(Target)
       JOIN [DocumentInfo] di
         ON di.StatusId = t.DocumentStatusId
            AND di.ReceiveDateTime &lt; CA2.Target
            AND NOT EXISTS (SELECT *
                            FROM   [doc].[document] d (NOLOCK)
                            WHERE  d.ParentId = di.DocumentId) 


It can do an equality seek on StatusId and a range seek on ReceiveDateTime