This is a rather belated answer but I was looking to find out how to do this myself so perhaps it'll be useful to others. In API level 18 the following service was introduced which should make this straightfoward as you can now get a callback whenever a notification is added or removed:
https://developer.android.com/reference/android/service/notification/NotificationListenerService.html
In particular for the original question see the onNotificationRemoved method
The other option mentioned by jpop above is to use the builder's setDeleteIntent method when creating the notification, which will give a callback when the notification is deleted. This would then require you to maintain the state of the existing raised notifications somewhere else as it only tells you when something is added, not removed.