Here's a couple of "clean" suggestions (ie: things you can do without resorting to force deletes). In your cinder.conf file, look for the 'volume_delete' setting - if it's not already, change it to 'none':

volume_clear=none

This allows Cinder to skip clearing the volume before deleting it. Also, look for 'lvm type' - if you can, consider setting this to 'thin':

lvm_type=thin

...in other words, use thin provisioning. This will allow Cinder to only delete blocks that actually have data written to them, which provides a useful speedup. However, this only works if you're able to use thin provisioning in the first place. :)