I would imagine they store the highest available quality only by default and do on the fly transcoding until a certain threshold of views per time is reached. At this point they would then store the transcoded versions as well.
For videos with a lot of views it only makes sense to store the transcoded version as, like you say, storage is cheap. But fact is that the vast majority of uploaded videos get <1k views and for those it probably would make more sense to transcode them otf when needed.