gistfile1.txt

SELECT cv.* FROM candidate_versions AS cv JOIN (
  SELECT lower_bound.candidate_id, MIN(lower_bound.updated_at) AS lower_updated_at, MAX(upper_bound.updated_at) AS upper_updated_at FROM (
    SELECT MAX(updated_at) as updated_at, candidate_id FROM candidate_versions WHERE updated_at <= '2009-01-01' GROUP BY candidate_id
    UNION ALL
    SELECT MIN(updated_at) as updated_at, candidate_id FROM candidate_versions WHERE updated_at BETWEEN '2009-01-01' AND '2010-01-01' GROUP BY candidate_id
  ) AS lower_bound JOIN (
    SELECT MAX(updated_at) as updated_at, candidate_id FROM candidate_versions WHERE updated_at <= '2010-01-01' GROUP BY candidate_id
  ) AS upper_bound ON lower_bound.candidate_id=upper_bound.candidate_id
    WHERE lower_bound.candidate_id < 10020
    GROUP BY lower_bound.candidate_id
) AS bounds ON bounds.candidate_id=cv.candidate_id
  WHERE
    cv.updated_at BETWEEN bounds.lower_updated_at AND bounds.upper_updated_at AND
    (some conditions)

Example data:
id,candidate_id,version,updated_at
1,1,1,2008-12-01
2,1,2,2009-02-01
3,1,3,2010-03-01
4,2,1,2008-01-01
5,2,2,2008-02-01
6,3,1,2010-02-01
7,4,1,2009-02-01
8,4,2,2009-03-01

With the above query we should get back the rows with id 1,2,5,7 and 8.