We present CONCERTS: Coverage competency based target search, a failure-resilient path-planning algorithm for heterogeneous robot teams performing target searches for static targets in indoor and outdoor environments. This work aims to improve search completion time for realistic scenarios such as search and rescue or surveillance, while maintaining the computational speed required to perform online re-planning in scenarios when teammates fail. To provide high-quality candidate paths to an information-theoretic utility function, we split the sample generation process into two steps, namely Heterogeneous Clustering (H-Clustering) and multiple Traveling Salesman Problems (TSP). The H-Clustering step generates plans that maximize the coverage potential of each team member, while the TSP step creates optimal sample paths. In situations without prior target information, we compare our method against a state-of-the-art algorithm for multi-robot Coverage Path Planning and show a 9\% advantage in total mission time. Additionally, we perform experiments to demonstrate that our algorithm can take advantage of prior target information when it is available. The proposed method provides resilience in the event of single or multiple teammate failure by recomputing global team plans online. Finally, we present simulations and deploy real hardware for search to show that the generated plans are sufficient for executing realistic missions.