There are some idiosyncracies that you should understand when working with large numbers of messages. Read more for a couple pointers…

If you are working with a large number of emails, (more than will fit
on one screen “page”) be sure to remember that checking “All” doesn’t
check all messages in the category you are viewing, but only those
visible on the current page. So, if you have three pages of messages,
only the first page will be affected if you click “All”.