Yours is certainly a logical line of thinking, but the code as installed with 3.0.4 on this site definitely makes no sense.
A quick search brings up lots of complaints in the last year alone about 404’s that sound similar along with intricate stories of how people got things to work. Perhaps under certain conditions the “paged” query value is filtered out, and the 404 handler expects that to have happened, but I didn’t find any evidence of any attempts to do such a thing.
The whole idea of: “Hey, I found a category as asked,” and: “If someone is looking for a specific page then puke,” seems, on the surface, a silly one.
But, I’m not suggesting anyone change anything — I just posted this in case someone is stuck.