So at the most there's not really a specific permission (you say "blanket license", Cornfed), right? In the UK (from what Brigs is saying), I'm assuming, you're just checking if the band is registered, not whether every single song you're going to perform a cover of is specifically covered by the arrangement? Yes/no? Is that actually happening in pubs & clubs? It doesn't sound even faintly likely that a pub that holds a live music license (which they would acquire from a local authority i.e. their local council) would be asking a band what specific bands & songs they were covering. I just don't think this is a requirement, legally or otherwise. Therefore, the original copyright holder is not in a legal position to stop performances of individual songs. Are the Iron Maidens going to stop performing this song? Cornfed's spoiler comment probably makes this most sense in this specific case at the present time.