The Mechanic Muse: From Scroll to Screen
nytimes.com
nytimes.com
These complaints are really issues of software, and UI specifically. The technology needed to add a "Go to random page" option to the Kindle is absolutely trivial; it's a matter of the UI developing enough that features like that actually surface to be given visual prominence equaling their demand. I really do find the experience of looking back a couple pages extremely painful on a Kindle; that experience is screaming for UI improvements (which are probably a lot easier on a touchscreen; I'm imaging something like iOS video scrubbing).
I'm sure it took at least a bit of time for the concept of codex page numbers to develop, and I'm sure until that point people thought "with scrolls, we could measure length to get a sense of position, and now we can only guess based on thickness"; I find this no different. The solution then was to think of a way to intuitively incorporate that need into the codex, not to give up on the codex and hang on to scrolls.
A more natural model might be that of single continuous page (a la scroll), maybe with controls to slide the text up a bit as you read. Of course this model is available on the web and on platforms like Adobe, but the hardware readers (Kindle, Nook) still use the page paradigm.