When deleting a page that is referenced by the menu, and in this particular case which was automatically added to the menu from the “Automatically add new top-level pages” setting, it isn’t automatically removed from the menu. The menu continues to reference the removed page and gives a WP error in response.
I think it’s been like this since nav menus were added, or at least I remember running into it a couple of times. I just tried it in 3.2.1 and it does the same thing – the menu item remains but it goes to a 404 because the page is in the trash.
RC2 is awful late, so no 🙂 It’s also not really an alpha/beta thing, since it’s been happening since before 3.3. Here’s a ticket on the issue (delete from menu happens with the item’s actual deletion, not trashing), might be more related ones out there: http://core.trac.wordpress.org/ticket/19038
Honestly, I personally don’t really find this unexpected; I would probably be annoyed if my menu items disappeared just because I accidentally trashed something. I just tested and the menu item is removed when you permanently delete it. Unless this is happening for you differently?