Are you looking at the number of "Records" or the number "Found"?
I believe I am looking at the total number - the number displayed after clicking "Show All Records"
Assuming you are in the same file each time you choose show all records, It is possible that your file is corrupted and that the file corruption is interfering with filemaker's ability to accurately count records. I had a filemaker 5.5 file that exhibited very similar behaviour. Sometimes a progress bar that displayed records remaining to be updated (such as in a replace field contents operation) would even display a negative number count. I could temporarily fix this issue by importing the records into a clone of the file. (To make a clone, choose save a copy as and specify the clone option). In my case, the problem would eventually return.
I finally fixed the file by completely rebuilding it piece by piece after converting it to filemaker 10.