Damn, Im going to have to re-install DK 1 & 2 now... PLAY TIME!
(now where did I put those disks)

Anyway, multiple models is one way, or you can tweak each models
vertices at creation time by a random amount. Just make sure
overlapping verticies (of touching blocks) get adjusted by the
same amount so they still 'mesh' with one another.
Note - I cant see this being very fast at level creation time though.

Another way may be blocks animated with bones. One bone per 'side'
with a "dug" position and an "un-dug" position meaning the block
"touching" that side is dug/undug. Warp the vertecies in med to be
a perfect mesh when "un-dug" but cleaner/smoother when "dug".
I hope Im clear with this difficult description.

PS Esper: Looking VERY good. Please PM me on how you got over
the slow level-create time(due to so many entities) if you dont mind.