You are probably already aware of this -- some important patents regarding video compression are coming up, particularly relating to MPEG4; I've talked to the attorney who is the primary examiner on this patent cluster, and he actually rejected some of them last September (from major multinationals) based on over-breadth. It's wait-and-see. PacketVideo has just gotten an important patent on an error reduction algorithm relating to video compression in low-bandwidth situations that could have been applied very usefully, had it been freely distributed.
One particularly broad and already much discussed patent in this area is at the basis of RealAudio:
Audio-on-demand communication system
It is doubtful whether the calculation rule covered by DE3629434 really took a long time to find. Also it is somewhat strange that a 12 year old patent was nominated "patent of the month". But it seems clear that the MP3 patents are showcased as cases of "good software patents", since they cover solutions to difficult problems and may involve some empirical knowledge.