XviD, lame, x264, faac, faad, liba52 - to všechno jsou knihovny pro (de)kódování licencovaných formátů. Jsou vydané pod GPL licencí, proč by tedy Google nemohl také vydat své knihovny pod GPL?
Samozřejmě legální jsou pouze zdrojové kódy. Jakmile budete distribuovat binární verzi, musíte zaplatit za licence na formáty. Ale to už je problém výrobců HW, kteří binární Android distribuují.