I remember reading some article about Red Faction and how it did things with destructible environments that haven't been done since pretty recently. It was actually pretty interesting, and touched on a lot of the stuff mentioned here. Indestructible walls had to be introduced because they believed at the time that games still needed goal structure, and you can't have that if you can just walk to the end of a level. Technology at the time only allowed a boolean process to determine density (too hard to blow up, not too hard to blow up), so it was really the only way of stopping that.
As for the structural integrity not being altered at all, I think it was because the objects and environments were never actually "destroyed". Rather, if you blew a hole in something, the actual structure would technically remain, but the engine would replace the texture and polygons with something like a portal in more recent games, allowing you to see, walk, and shoot through it.
The article also mentioned something about a new game coming out with alterable environments. To be honest, it looked pretty retarded and wasn't the same thing at all. You could set off bombs that would basically liquefy the ground into something like magma, which when then harden and stuff like that. The effect looked pretty bad.
