That is, construct DELETE statements 100 or 200 ids at a time. You might also be able to do a DELETE LOW_PRIORITY which makes sure no reads are pending when the delete happens.

The MySQL manual says the size of IN is limited only by the maximum packet size. And that if they're all constants of the same type as the comparing expression, it sorts them and uses a binary search. I think your DBA is talking through his hat.

Wade.