In my estimation, the amount of memory it takes to keep an individual list of decals on every static surface in a map is a LOT less than modifying the textures themselves. (A few vertex locations, texture coordinates for each vertex, and a reference to a texture object takes up a lot less memory than keeping a separate copy of an entire wall texture to accommodate a bullet hole).

The most complicated part of it is taking a quad decal and getting the intersection between it and the wall surface so it doesn't stretch past the edges. The rest is just performing a little Z-bias after the static surface is rendered then rendering all the decals without depth.

When I first explored decals, I wondered if the wall textures were modified. When I realized I could prepare a lightmap first, then modulate the wall texture with it and modulate the decals as I render them, I realized modifying the wall texture wasn't necessary to ensure the decals are properly lit.

You're asking why, when a player gets shot, we don't find the corresponding piece of texture, lock it, draw a bullet-hole, unlock it, then continue rendering as normal? There are several reasons, in no particular order:

First, it's more difficult than it sounds. Triangulating and inverting a set of texture coordinates to find the UV of the bullet-hole isn't mathematically trivial.
Second, locking a texture introduces nasty performance penalties. As things stand, the texture is sitting neatly in VRAM, maybe even in the cache. In order to change the texture, we'd have to lock the texture, causing a pipeline stall (to ensure that the texture isn't used while it's being changed), paint the new texture up and upload it back to the card. If this happens every time something gets shot, we could be stalling the pipeline very often.
Third, the mapping of the texture onto the mesh may not be affine. In other words, square bits of texture don't have to appear square on the geometry they map to. So now, to avoid weird-looking stretched bullet-holes on screen, we need to draw complementary weird-looking stretched bullet-holes on the textures. This itself can introduce a visual inconsistencies depending on the resolution and anisotropy of the drawn decal.
Fourth, textures are often shared among meshes. If we start paint-balling one mesh, we wouldn't want all the others to come out with sympathetic injuries. The need to keep a separate copy of the texture for each mesh severely outweighs the cost of drawing a new primitive.

I can think of a couple of less significant problems, but this should be sufficient evidence to put you off the idea.

Now if you consider that drawing a decal as a blended triangle/quad on top of existing geometry involves transforming a negligible 3/4 vertices, and performs the pixel-blending just as you would have to in the first place, only on the GPU where it's lightning-fast, a clear winner emerges.

Edit: I need to spend less time typing and more time posting [rolleyes].

Admiral