Update (June 2013): This no longer works. Try another trick.
When you search for something in Gmail and there are many search results, you'll see a vague message like "1 - 20 of thousands". In other cases, Gmail shows that there are about 80 results, when the real number is 78. But what if you want to find the actual number of results instead of an estimation? If you have the new version of Gmail, it's really easy to add more precision thanks to permalinks.
(Small digression: I'm sure that Opera users will stop reading this post because Gmail 2.0 doesn't support their browser, but the User JS file from this page fixes the compatibility issues and you can use the tip below. )
Let's say you want to find the number of conversations that contain Google, but don't have the label .Comments. You will search for:
google -label:.Comments (a shorter query: google -l:.Comments)
The address bar should display this URL:
If you go to the next pages of search results, you'll notice that Gmail appends /p2, /p3 etc. to the previous URL. To see the actual number of search results, force Gmail to display an arbitrary page. For example, you can display the page #1000 if you estimate that the number of search results is smaller than 20*1000=20000. Just append /p1000 to the address and get something like:
or more generally:
Unfortunately, if you manually modify the address, Gmail no longer updates it when you go to a different section, so you need to refresh the page.