Before we start, let's make sure to understand the problem entirely. The problem states we've to find the year.
Binning them by month will not give any advantage to filter by year.
Binning them before 2000 and after 2000 is a good one, but it's only two bins. Remember, we could still have a lot of people that belong to each of these two bins. Considering 20 people in the room, the factor of reduction by this strategy is only (20 - 1)/(20/2 - 1) = 19/9 = 2 (approx). Needless to say, here we're assuming an equal spread of people across the bins.
Now, binning them by decade might work out much better, since we have a very good possibility of old-middle aged-young people in the crowd. again, assuming we have a good spread across our bins, this could give a much better factor in reduction (though to quantify this, we must've access the actual data).