Okay, I've isolated what appears to be part of the problem, and something I overlooked in our upgrade from 2.2 to 2.3: We also split the existing tree into multiple BDB backends. Several isolated branches of the tree were quite large, and this was an attempt to split the database in multiple, more-managable chunks. We were also looking at partial replication of just one portion of the tree.
Now, as I muck about on a test server, I see that if I edit slapd.conf so that only one backend is enabled, I have functional paged results. If I enable a subordinate database, paged results fail with the previously mentioned "old or invalid" error.
So, at least I have a fallback plan to get this working: merge it all back into the single BDB database. I'd like to avoid that if I can, though.
Are there tricks to using the paged results control when searching across multiple backends?