|How long have you waited before shutting down and trying again? |
It's possible that one part of Windows is telling you that the program is not responding only because the app is taking longer than expected to complete it's task.
Try emptying your Outlook Deleted Items folder then try deleting the email and giving it a lot of time. Go to bed, go to work, go camping. If it's still not responding when you get back, then we'll take it from there.