The simple, but not-so-clean way, is the route you already took, but with an additional, small module to help it.
- has a function my_module_can_delete($user), that returnsTRUEif the user is allowed to delete,FALSEif the user is not.
- implements hook_form_alter()to modify and delete the button on the node_edit form, ifmy_module_can_delete($user)
- implements hook_form_alter()to modify the confirm form that is called on /node/%nid/delete, and add a message there, telling the user he or shemy_module_can_delete($user). This should be enough, since disabling this form will result in users not being able to get past this form. FORM-API will take care of that.
However, you can make it more sturdy, to catch other deleting modules:
- implements hook_nodeapi(),$op == 'delete'to catch delete actions and halt (by invokingdrupal_goto(), or callingdrupal_access_denied()to enforce a user-error. Only catch delete-actions if the referer was the delete-confirm-form as mentioned above. Or, more secure, whitelist your VBO-action and return false on all other referers. A referer can often be found by reading out the $node passed along tohook_nodeapi().
A, IMHO, much cleaner, but probably more intensive alternative, would be to simply make sure your batches/actions are called on every delete action. 
In a module, you could do this by avoiding all the VBO-configuration and leaving all the extra-delete actions out of there. 
Then write a module that implements hook_nodeapi() and then calls all the cleaning actions from there. That way you can be sure that your delete-actions are called on every delete-action on any node. Obviously you can add some conditions into your hook_nodeapi() to only invoke your modules in certain cases (node-types, user-roles, permissions and so on).