Kodeky jako takové vesměs u nás nelegální nejsou. Nejde totiž o porušení licence, tyto jsou obvykle v pořádku, GPL nebo LGPL rozhodně běžný uživatel porušuje těžko. Problém je s patenty k algoritmům, a ty se vesměs týkají osob za oceánem. DeCss je pravda asi jiná kategorie, ale vzhledem k neochotě(čti neschopnosti) vydavatelů dodat ochranu takovou, aby obstála i při znalosti algoritmu (open source), se s tímhle dá těžko něco udělat. Nikdo mě ovšem nenutí takovou knihovnu mít.
Jinak s těmi kodeky je to velmi podobné i na těch Windows. Windows XP pokud vím vůbec nepřehrají v základní instalaci DVD, protože jim na to chybí kodeky. A doufám že opravdu nečekáte, že úplně všichni mají ty kodeky na svých windows získané vždy legálním způsobem :-) Takový kodek na h264 je kvalitní, ale ne zadarmo. Pravda, ve Windows 7 už mají celou řadu kodeků ve výchozí instalaci, což je jistě plus pro Windows.