Floyd cites MP3, which German police have been actively policing at trade shows like CeBIT. They're not really acting as patent police. They're looking for pirated content, and the means to reproduce it. But patent claims give them the power to go after everyone, even if they're using FOSS software to encode their stuff.
I think there's a difference between how seriously police take patent claims at a trade show and how they take calls from Hollywood to seize stuff. Patents in this case are just an excuse to enforce copyright.
But I take Floyd's point. Digital content is a patent minefield, and each country has its own set of mines.
This still does not render the success of VLC or Google's move with VP8 meaningless. Despite all the policing in the world the trend is toward more open audio and video formats, to less DRM, and to complex files being given the same rights in the online world as simple files like this one.