This issue occurred in our production environment.

Space 1 has label "project-planning", and there are 27 items with that label
Space 2 has label "project-planning", and there are 11 items with that label

Open Space 1 -> Browse Space -> Labels -> All Labels
Select "project-planning" label
It displays a page with 10 results. At the top of the page it indicates there are total 27 items.
When user clicks on "Next >>", the total number of items is changed to 38! (total 4 pages)
We can navigate to the items after 27, and we see the items from other spaces with the same label.

I guess the problem is happening because there are other spaces having the same labels. So, if we search on a label from one space, only the first results page will show the correct number. Rest of the results pages show items from all spaces.

It looks to me like Confluence resubmits the search for each page, and doesn't manage to preserve the "in space" restriction.

The same problem occurs on Atlassian's own wiki in their Confluence space (http://confluence.atlassian.com/display/DOC/Confluence+Documentation+Home).
We don't see it in the current issues list. We think it is a bug, that it is not limiting the search to the current Space (after page 1 of results).

You may contact me or "Paula.A.Matuszek@gsk.com" if you have any further questions or if there is any update on this bug.