There also seems to be ‘something’ going on when there are more pages in the wordpress site than appear on a single Page section page (basically when pagination happens in the Page pane of the Appearance Menu page)
This post seems to have the same problem and a solution (http://wordpress.org/support/topic/missing-pages-in-appearance-menus-pages?replies=6)
To quote the solution that solved this problem for me:
Changed the $per_page value from 50 to 5000 in wp-admin/includes/nav-menu.php line 587 and the problem disappeared.
