When I create a new node and give it a menu item at the same time on the node-editing page (under Menu Settings) and Submit, I get two messages: one telling me the menu item has been created and one telling me the node has been created.
When I edit that same node and submit, I get two messages: again one for the menu item and one for the node.
However, when I edit the node and delete the menu item (via the node-editing page by ticking the "Check to delete this menu item" box), I only get one message telling me the node has been updated.
Apart from being inconsistent, I then had to go check to see if the menu item really had been deleted. It had. But I think the user should get a message saying the menu item has been deleted.