The watcher of the issue does not receive notification when the issue is deleted. This is tested for JIRA 4.0.2 and JIRA 4.1.1.
The watcher has permission to 'Browse Project' and the Issue Security Scheme is not associated with the project. In addition to that, the default Notification Scheme is used (whereby, Reporter, Assignee and All Watcher are added as the recipient of the Issue Event).

Here are the steps to replicate the problem:

1. Create an issue and assign it to a user
2. add the watcher
3. delete the issue

The Reporter and Assignee get the notification when the issue is deleted. However, the issue watcher does not receive the Issue Deleted notification.