They will, either elsewhere on the island (Brooklyn, maybe), or by having a new owner, or when the lease on the NC expires in 2015.
The point is that the financial base (fans, corporations, NYC in general) is too significant for the team to be uprooted. If the Canadiens or Leafs were stuck in a bad lease, that wouldn't mean they'd leave. The Penguins used the threat of moving to Kansas City to secure a new arena, but no one seriously considered that they'd actually leave (similar to the Oilers mulling over this tactic). It's different than other circumstances (like Winnipeg, originally, or Phoenix, now) where there were issues with the city/area being able to support the team financially. That's a problem that's much more worrying to owners and investors, and a lot more difficult to fix.