A parity problem

This is an interesting problem I came across when participating for fun in a contest (it was an online mirror of the finals, so it was an unrated match)

Source: Codeforces Bubble Cup 8 - Finals, Problem D (Tablecity)

Problem:


There is an 1000 x 2 grid,and a thief is located in one of the cells (we don't know which one). In every hour, the thief moves in one adjacent cell either to the right or to the left as in the picture above.

You need to catch the thief but in every hour you can assign only two policemen to search two arbitrary cells. If the thief is inside one of the two cells you are searching, you will catch him.

Describe a strategy which ensures that you can catch the thief within 2015 hours or less regardless of where the thief was located initially.

Analysis (without solution):
At first sight, this seems to be quite difficult. How can we catch the thief if he keeps moving?
Well, we could try to corner him but we must also assume that the thief knows our strategy and he can try to counter it.

It seems intuitive to put the policemen in blocks of 2 like this (since it's a 1000x2 grid):

We can then move the policemen, by one column to the right each time to somehow corner the thief.
That seems to be our solution! But there is a fatal flaw with this strategy:

 

In the above case, if we are moving to the right and the thief is in the adjacent column, he can bypass us in the next hour and jump to the left (we will thus not catch him):

So any ideas on how we can solve this problem?
Feel free to post your ideas or even your solution in the comments.

EDIT: Solution posted here.