Okay here we go. It is a bug in WordPress itself.
I have already shortly explained the issue in my question, so either have a look at it or check out the ticket linked above for more details.
Until the issue is properly resolved I propose this dirty, dirty hack. It is based off the idea that as soon as another sub-menu that is accessible is added everything is working fine again. So we temporarily add a dummy submenu-item just to trick the check and then remove it immediately.
function workaround_issue_22895(){
add_submenu_page( 'edit.php?post_type=page', 'Workaround_Issue_22895', 'Workaround_Issue_22895', 'edit_pages', 'workaround_issue_22895' );
add_filter('add_menu_classes', 'workaround_issue_22895_unset');
}
add_action( 'admin_menu' , 'workaround_issue_22895' );
function workaround_issue_22895_unset ($menu){
remove_submenu_page( 'edit.php?post_type=page', 'workaround_issue_22895');
return $menu;
}
BTW, have I mentioned this is a dirty, dirty hack you should handle with care?