Pages History is one of the few tools in the suite that does not have any caching. It would seem from looking at the Apache logs that some people are rapidly requesting results for the same page -- which should trigger the rate limiting, but somehow they're getting around that.

Regardless, caching would help.