Oh man, this is interesting. I think I already have my answer, just from pondering your response and trying a few things, but if you can try something for me, it would help.
By the way, it has nothing to do with notifications - I was just using that to show the issue.
So, here's how to show it. Change the menu item in KM then immediately switch to mail. Chances are it will show the old menu item.
If it doesn't, wait for the notification message to go away (so there's no confusion), switch back to KM and try it again. Don't wait long at all between when you change the menu item and you switch to mail. Use Alt+Tab or whatever works on your system.
Assuming this shows the issue, I think you'll be able to deduce what's going on, and it will confirm my theory. I hope.