I'd be surprised if you couldn't drop your own gstreamer plugins into Opera's directory on Windows/Mac.
You'd be surprised at the hundreds of millions of XP users with codec packs installed already. For the remainder Mozilla would just need a nice 'codec not found, go here' dialog like they already have for Flash.
I can see Firefox doing similar on Linux, so if it's just (ironically) the Linux geeks that are desperate for the patented codecs then I wouldn't worry too much about it. For the 60% of Firefox users on XP though, Mozilla aren't going to rely on system codecs that aren't there.