Are you making the Nagios host pull (via NRPE) or are you asking the individual hosts to push (via NSCA)? I am trying to solve a similar problem. Given a dynamic population of hosts, each of which has a variable life span, I think that asking individual hosts to query their own state and then push that to a "monitoring receiver" is the most scalable, sustainable approach. At least, that's the theory I'll be testing this week.