There's nothing necessarily static about BSPs - in fact level editors use BSP brushes (other piecces of geometry stored as BSP) - exactly because calculating set operations between BSPs is fast and well defined, and results in another BSP.

In fact, Red Faction, one of the first games to feature destruction on the PS2, used BSPs under the hood instead of voxels/marching cubes.

What was expensive, and made these game levels static is, was the occlusion calculation and light maps, which were relatively expensive at the time, and the fact that the first instances of those engines, like Quake were designed for the Pentium.