There is always more than one way to skin a drupal, but they are rarely of equal merit.
It sounds like you have a page that is using Views Bulk Operations? If that is the case, find the view that generates the page and remove Delete from the operations selected.
If that is not the case, but you would like it to be, then see if the page in question is covered by Admin Views. Enable the module, find the related view, and modify it to suit you.
If that also is not the case, then fortunately for you this interaction is a form of some type. You can use a hook_form_ID_alter() function to change the
global $user; $user->roles array so you retain the delete function for yourself.
If you want to let the user in question retain the Delete option, and just fail when they select that for a nodetype that is out of their permission range, then use drupal form validation. This lets the form stay as it is, but if your check of the node types selected does not match up with the current user's roles then you can just fail their action before it reaches the next screen.
There is always more than one way, they may not all work for you but one of them should. If none of these match your need then please update the question.