How can I theme "Error generating image." error 500's in Drupal 7?
You can't.

This is hardcoded in http://api.drupal.org/api/drupal/modules--image--image.module/function/image_style_deliver/7.

You would need to completely override this page callback to change what it does. You could do this with hook_menu_alter() but that means that you would need to make sure that you also apply any upstream changes to that function to your own copy.

Can't you just leave the images there instead of deleting them? And if they are just a temporary resource, maybe exclude them from search with robots.txt?