Ok, this seems to be a known behaviour:
http://world.episerver.com/Support/Bug-list-beta/bug/33750/
Although there is a setting to revert some of the peculiar behavior, the wastebin part of it remains. I find this really odd, but it seems I'll have to look elsewhere to find a workaround for really getting to know when a page is deleted, regardless of how.