When manipulating configurations (add/delete), admin_menu items are cached and stay the same.
Suggestion is to call cache_clear_all() on configuration creation and deletion.

P.S. probably the same with editing, since the name might have changed.