Here's one possible (but highly incomplete in its definition) way for the program to handle moving terrain, as a reference for future considerations:
1) moving terrain is organized through a logical object known as a container. A container is a transparent frame (the frame itself is not visible though) that "holds" a set of terrain pieces (or using the current way to dealing with terrain, the actual terrain pixels) and also a set of interactive objects. Containers also have a position within the level, a defined route it will execute throughout the level, as well as various parameters defining how the container will move through the route (eg. speed). When the container moves, its contained elements move with them. This includes the contained terrain pixels and interactive objects, and possibly one or more lemmings during game time.
Different containers can intersect each other, either as the initial level setup, or more likely at some point during game time. There is a z-order associated with containers, so that when objects from different containers overlap, when painted on the screen one will obscure the other based on the container z-ordering. Intersecting containers do not interfere each other's movements, just as lemmings move through each other. Notice that the terrain pixels from different containers are kept track of independently, even when an intersection of containers occur.
2) All levels have at least one container, whose size spans the entire level area and its stationary. This is the "default container" for holding terrain and interactive objects.
3) The tricky issue of course is how lemmings fit into this. A scheme is needed to define when lemmings transfer from one container to another, and also how their positioning is affected when they are contained in a moving container.
The general idea though is that, as long as a lemming is always associated with exactly one container at any time, then the pixels resulting from builders are also associated with said container. Excavation should result in pixels of the lemming's container from being removed, although it's still an open issue whether pixels from other containers might be removed as well, in situations where there are overlapping of terrain pixels from different containers.
This area still needs to be worked out, but one idea is that whenever the lemming is falling, he will be transferred to the default container. Landing is defined to be when the lemming's current position is a terrain pixel from any container, at which point the the lemming is re-associated with the container. If at that pixel position there are multiple pixels from different containers, the game chooises one container, say the way with the highest z-order. (This is in line with how the game currently handles overlapping interactive object trigger areas.)
Anyhow, this is the tricky part that needs to be worked out with some thought, but hopefully this helps define a starting point for how to implement the moving terrain idea sometime in the future (probably not the near future, but anyhow).
It should be noted that from a level design point of view, I definitely do not recommend purposely creating situations where terrain pixels or even interactive object pixels from different containers overlap during the course of the game. However, this is practically impossible to accurately check for at level-editor time (unless you're willing to be very restrictive), and given that the terrain pixels for a container is not fixed anyway (due to excavation and bridge building), in a sense it is truly impossible to check for. This is why I believe for simplicity the game engine needs to consider situations where pixels from different containers might overlap. The simplest approach would of course be to treat pixels from different containers as independent, but this needs to be carefully orchestrated with the behavior of the lemmings and the player's intuitive expectations.