I would disagree with that. The Devils were successful for 20 years and you can't sustain that kind of success with out core players changing. Detroit I think is a pretty great example of that. They went from Fedorov, Yzerman, Hull, Robtaille, to Datsyuk, Zetterberg, etc. Maybe Holland lucked into a couple late round franchise players, but there was still a major transfer in power on that team.
NJ went through something similar. At first it was John MacLean, Scott Stevens, Scott Neidermayer, Bobby Holik, then Elias, Arnott, Sykora, Gomez came along, and then after that Zajac, Parise, Langenbrunner. Lou had a philosophy of not giving up on a season and he wouldn't give up on players with expiring deals because he wanted to put the best team on the ice, but I would still consider that "rebuilding on the fly" because the team was so successful for so long.