Saw this indication today on my inbox:
   1 – 45 of 31

Strange counting...
;-)

Weird! Do you have offline gmail activated?
And by the way, now I see the count in "All mail" going 1 – 100 of 22780. Is this new? Am I wrong or it previously said "hundreds" like when you do a search?
About search: I did a couple of random queries and the count says 1 – 20 of 80, then I click Next, and says:
21 – 40 of about 110
[Next]
41 – 60 of about 130
[Next]
...
and starting from 121 – 140: "of about hundreds" (it says this when goes over 200)
But why it says 80 at the beginning and then increases? Does it go "deep" in the search as we read results?

After refreshing the count was the correct figure...

I have disabled offline access because you can't control local storage...

The same thing is happening for me in regular Gmail. I do a search for a simple word that appears in many of my messages. The Search Results show:
   1 – 20 of about 120

I click on "Older" and the display now says:
   21 – 40 of about 140
I keep clicking, getting the following results after each click:
   41 – 60 of about 160
   61 – 80 of about 180
   81 – 100 of hundreds
   101 – 120 of hundreds
   121 – 140 of hundreds
...and so on, until I get to the end:
   221 – 222 of 222

What in the world is going on here? This seems like a pretty silly bug. It would be nice to be able to know the number of messages found without having to click through ten pages of results to get to the last set and see the REAL number of found messages.

By the way, refreshing doesn't fix it for me.