Scalable multi-parameter query

As martin comments on one of the answers, some care is needed here to only return rows where all 3 values match. One way to do that is to add a formula field to the SObject that concatenates the 3 values in a distinct form and then query that:

List<Items> items = new List<Items>();
items.add(new Item(1,1,2));
items.add(new Item(2,2,2));
items.add(new Item(3,3,3));
items.add(new Item(1,2,3));

Set<String> keys = new Set<String>();
for (Items i : items) {
    // Same pattern here as formula field added to SObject
    keys.add(i.prop1 + ':' + i.prop2 + ':' + i.prop3);
}

List<ItemInDB> itemsInDB = [
        Select Id, Name 
        from ItemInDB
        where NewFormulaField in :keys
        ];

PS

Responding to the comment about matching varying numbers of properties, I think using like and wildcards would work:

        // Match 1st and 3rd and any value for 2nd
        keys.add(i.prop1 + ':' + '%' + ':' + i.prop3);
        ...
        where NewFormulaField like :keys