I wonder if techniques from differential privacy could be helpful here (in terms of the multiple-querying problem).