Bricksmith doesn't just put each part in a VBO - it also builds (on the fly per render) an instance VBO - that is, a VBO full of transform data and color - for each part (e.g. a 2x4 brick), the VBO is drawn once* with an instance buffer describing where and what color each use of that part is. The entire instance buffer is built once and sent to GPU memory, then each part is drawn once using part of the instance buffer. This gives Bricksmith both minimal draw calls (one draw call per change of part) and minimal per-render GPU memory overhead (because we write all of the instance data into one big buffer).
The one exception is translucent parts, which are drawn later in Z order from far to near, even if this means changing VBOs per part.
The one exception is translucent parts, which are drawn later in Z order from far to near, even if this means changing VBOs per part.