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.