This week's book giveaway is in the OCPJP forum. We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line! See this thread for details.
Chuck, A few things that come to mind: 1) First thing is to check you have an index on column one and column two. 2) Are the values in the columns distinct? If there are duplicates you can merge some which would slightly optimize the query. 3) Try an experiment where you break the query up into batches on 10-50 in clause sets each. This will ensure that the extremely large prepared statement isn't too big to deal with in memory.
Bear, I don't think an in clause would work here. It would end up returning more rows because it can only check for one condition at a time.