You should really try to figure out why it is failing in the first place. Set debug=True and verbose=True in cinder.conf, restart the services and make a further delete attempt to see if anything useful pops up in the volume log file.
You can also try using the cinder force-delete command, which bypasses some checks.
Last but not least, if you're sure the volume isn't there anymore and there are no references to it (eg. in /etc/cinder/volumes), you can hack into the database and delete it from the volumes_metadata and volumes tables.