Joannesalfa
Your idea is kind of like the original spelunky If I am correct:
In the original spelunky, every object outside an area ,bigger than the screen, around the player don't exist; they exists once more when the player come close enough. But in your case, it could be a fixed area like in pok?mon Red/Blue/yellow (when you leave a town, people and events diseappear), also reminds me of megaman and other zelda <img src="smileys/smiley2.gif" border="0" align="middle" /> (not for ennemies, but for key objects that sometimes would be difficult to get the track of).
If so, I second this, we could build bigger level that way without too much trouble, but we have to be aware of problems that come with it (in the original spelunky for exemple, a bullet that go outside the active area stop existing, when you go all-around the area, then comming back the other side, the bullet is back, and you are kind of dead if unlucky)
EDIT: But I am not sure if destroying/recreating is a good way to go