Page remove emails aren't being sent when the page is initially removed (moved to trash), they are only sent when the trash is purged.
A new event, and associated email notification, should be generated when the page is initially marked for delete.