Battlefield franchise manages it though? Has done for a decade or so now, which in computer terms is a f**king lifetime.
Granted not everything can be damaged, especially in city environments with loads of buildings, but still it's better than nothing.
EA DICE is the developer for both of those game series as well.
Battlefield is very careful in the level of destructibility it allows though; almost 'scripted' rather than a generic free-destruction-for-all type affair. It's certainly a nice to have and can really add to the immersion and enjoyment without a doubt. It's a big step away from totally free destruction though (unless that destruction is purely cosmetic and doesn't affect the players in any meaningful way). It's the network complexity that really restricts multiplayer and networked games (or, rather, keeping everything in sync when 10 players might have 100meg connections with 20ms ping and another players might only have 1meg connections with 150ms ping times). That's one of the reasons we don't really see massively multiplayer FPS games; for every player the system has to communicate the players' positions, velocity, animation state, etc. Then, for example, consider that 64 players are online together and using machine guns firing multiple rounds per second. Suddenly that's 64 players' worth of data to be kept in sync plus several thousand bullet / projectile positions, velocities, etc. Then vehicles. Incidental characters. It all adds up and absolutely must stay in sync if the game world is to remain consistent for all players. Then, on top of all that, trying to add in things like generic tables, chairs, and other physical objects that can affect a player - you suddenly have thousands of physical objects with tens of thousands of properties that have to be consistently communicated across the network. It's a pain to get working and a real barrier to making much more immersive gameplay experiences. Hence the reason why, as you rightly say, it can be a bit disappointing to see how 'static' things can appear in-game, especially given how rapidly things have advanced in computing and gaming over the last 15 years.
(Sorry, didn't mean to write an essay! Just trying to explain some of the reasons why it's such a pain and why some of these restrictive game designs come about!)