The guy behind Atomontage has stated that he's got his engine averaging less than one bit per voxel (he estimates 753 bits or less per 1000 voxels)[1] by applying a variety of compression mechanisms[2], so at least that part of Notch's assessment can be disregarded out of hand.
EDIT:
Taking a step back, remember that with an octree, contiguous areas require less tree depth to fully describe them, so open empty space (sky) and consistently filled space (uniform material underground) require much less data. This of course creates practical limitations in addition to the claimed maximums of what the engine can achieve (so art budgets aren't going anywhere anytime soon) but I think calling it a "scam" is a bit much.
Nope, more like 2 petabytes plus 1 bit. Because almost all of that new top 8m is the same atom (empty air), if they are using an octree to store the voxels, then it would take 1 extra bit to store an empty top 8m. Obviously if there are things in the top 8m, it will take more space, but only for the things that are there.
EDIT: Taking a step back, remember that with an octree, contiguous areas require less tree depth to fully describe them, so open empty space (sky) and consistently filled space (uniform material underground) require much less data. This of course creates practical limitations in addition to the claimed maximums of what the engine can achieve (so art budgets aren't going anywhere anytime soon) but I think calling it a "scam" is a bit much.
[1] http://www.youtube.com/watch?v=1sfWYUgxGBE
[2] http://www.atomontage.com/?id=tech_overv