For those missing vol_id (/sbin/vol_id): use blkid instead.
On debian lenny, the udev package has a binary named vol_id which can create some nice uuid's for block devices / volumes.

On debian squeeze, the binary is gone! Eee gads! Not to worry, blkid will do the trick.