DNS is widely abused by Internet criminals in order to provide reliable communication within malicious network infrastructure as well as flexible and resilient hosting of malicious content. This paper presents a novel detection method that can be used for identifying potentially compromised clients based on DNS traffic analysis. The proposed method identifies suspicious agile DNS mappings, i.e., mappings characterized by fast changing domain names or/and IP addresses, often used by malicious services. The approach discovers clients that have queried domains contained within identified suspicious domain-to-IP mappings, thus assisting in pinpointing potentially compromised clients within the network. The proposed approach targets compromised clients in large-scale operational networks. We have evaluated the proposed approach using an extensive set of DNS traffic traces from different operational ISP networks. The evaluation illustrates a great potential of accurately identifying suspicious domain-to-IP mappings and potentially compromised clients. Furthermore, the achieved performance indicate that the novel detection approach is promising in view of the adoption in operational ISP networks. Finally, the proposed approach targets both Fast-flux and Domain-flux, thus having an advantage over existing detection methods that identify compromised clients.