Just an idea. Are there any duplicate rows in the table? If not, how about, e.g.:

select column_1
from theTable
where column_2 in (123, 124)
group by column_1
having count(*) = 2
[download]

I am not sure an index would even help in this case, but I'd at least try one on column_2.

Update: As indicated by tall_man below, the effectiveness of the index will depend on the distribution of the data in column_2.