Well, partial success again. On the up side, Z-axis assembled from the linear rail and bearing sliding elements does work; there is no play and the motion is nice and smooth - see the video.
On the down side it is still not pulling out the drill bit from the mat completely. I have two possible explanations - since it's a belt drive, Z-axis with mounted Dremel flex shaft slides down from vibration at the short moment the steppers are disabled; or the motor simply doesn't have enough juice to lift the axis and pull the drill bit out of the mat at the same time (there is apparently some resistance). I can't find the torque curve for this motor, so I think a safe guess is that at least 25% of rated holding torque of 60 oz*in is available at 100 IPM (which is the up-stroke feedrate). This translates into almost 3 lbf at the pulley, which may or may not be enough.
I broke a couple more bits, though seeing this coming I had bought three four-packs. In the picture it can be seen that the bit was pulled out of the first hole, which would support the version that the axis "falls" at the moment steppers are disabled (after the up-stroke). However, I'm not too sure of this. I think I'll simply try hardcoding Z enable pin to 1 to rule this out. If this is not the reason, then the axis is too heavy for the motor and perhaps I need to look into using multistart leadscrew.
UPDATE: Yay! Hardcoding Z enable pin to 1 does help, which means that the Z axis indeed "falls" when steppers are disabled. Here is the video of it in action. The speed is about 1 hole per second, which translates into almost 8 hours to drill 9"x12" area. I'll try speeding it up even more. /UPDATE
The linear rail was quick to assemble; it took several adjustments to align the bearings in sliding elements to eliminate play, I also had to add the spring lock washers to prevent the nuts holding the bearings from turning loose.