For what it's worth, I don't know what YouTube's actual constraints look like, but it doesn't seem implausible that they might still be open to reencoding their top 10k video. After a billion views, you might get some substantial savings.

EDIT: After all, they did implement VP8/9 ;)