If I got your question right, and you want posts created/modified between 3 years ago and today, try this query:
SELECT p.ID, concat('http://www.toronto.com/restaurants/', p.post_name)
FROM wp_posts p
WHERE p.post_type="restaurant" AND p.post_status="publish"
AND p.post_modified > DATE_SUB(now(), INTERVAL 36 MONTH);
Because your DATE_SUB returns something like this: NOW – 3 years, so, it’s something along the lines of 2011-09-20 12:21:41.000000, and you are using a < sign, so you are checking for post that were created or modified before that date, so instead of getting the post created/modified between 3 years ago and today, you are getting the post created/modified more than 3 years ago.
Also, you aren’t getting revision, because as you specify the post_type="restaurant", and revision have a post_type called revision, you are just getting the post that belong to the custom post type you specified.