From what I saw in your post #18, when you were getting the high counts, the time period is not 1000 microseconds, but closer to 2000.
The serial print statements are slowing down the loop. At 115200 baud, and 10 bits per character you get 11.5 characters out per millisecond.
I'm not sure what you can do with serial output every millisecond. 
we definitely get improvement when we reset the reference times AFTER the set of serial.print lines.
It makes the measurement period more discontinuous, but that might not be an issue. That is, you alternatively measure for a millisecond, and print for a millisecond
You can always divide the number of counts by the actual measurement time period to get Hz.