The act of categorizing something does not affect the rewrite rules, unless you have put %category% in your permalink structure settings.
I never said it did (and that would be 'unless you put %category% or a non numeric setting FIRST in your permalink structure' if we wanna nitpick, but I get that you get that :) )
What I said was that if you use too many pages, you can bog down your site. And that's still true. Even with 'correct' permalink rules (%year% whatever). Not because it has to go through the pages FIRST, but because it has to go through ALL the pages (not to mention that I believe the rules are all stored in your options table, which can get pretty darn big if you have a lot of pages... there was a trac about this I read not long ago). I don't know how many pages you're talking about, but given that you're at the point where you want to apply categories to them, I'm going to assume upwards of 50 pages and not 10-ish.
If you google wordpress too many pages there are a significant number of people who've run into problems with it.
Aside of all that, you can have better 'structure' with posts. They're simply more flexible with permalinks, CPTs, tags, etc. They've got what you want, and they're just as 'doable' as trying to update an old plugin.