I've heard from Netflix people that they re-encode their entire library every month. They are continually improving their encoding and storage tools so the streaming bandwidth/quality savings dwarfs the costs of re-encoding.