Gmail bug with label and Select all conversations

It seems I discovered an annoying bug with Gmail: Labelling a selection doesn't work with "extended" select all (selecting all messages in all results, not only the present page).

Summary

Impossible to add labels on multiple page result at once. Each page must be labelled separately (once per page, not once per conversation, fortunately!)

Steps to reproduce

1. Go to Settings, Labels and create a test label. Say, Dummy label.
2. On the main page, Enter the following query before:2009/06/01 (this is what I used because I wanted to select old mails). Be sure the result will span over multiples pages; if it doesn't just create a search string that will.
3. Just for checking everything else works fine: open the first result and add the Dummy label to it. It should now have the Dummy label, as expected. Then remove the label to reset.
4. Just for checking everything else works fine: on the main page, check the first result and add the Dummy label to it. It should now have, again, the Dummy label, as expected. Then remove the label to reset.
5. Now select all by checking the checkbox over Search results. Since it is a multiple pages search result, a message will appear atop the list, saying All xx conversations on this page are selected. Select all xxx conversations in Search results.
6. Add the Dummy label to the selection. All the messages on the page will have the Dummy label label. Once again, this is the expected behaviour. So far, so good. Remove the label to reset.
7. Now the tricky part: again select all by checking the checkbox over Search results. Since it is a multiple pages search result, a message will appear atop the list, saying All xx conversations on this page are selected. Select all xxx conversations in Search results. This time, do click the Select all xxx conversations in Search results.
8. Then you'll get it. No conversation had been selected!

Thus: incompatibility between adding label and select all on all pages.

If you cannot reproduce, please specify at which step it stop working like I described.