Currently, the next, previous and page number navigation links for the newest questions are related only to the total number of questions and are of the form:
They should instead be related to the questions that are currently being displayed. The URL might be similar to:
https://stackoverflow.com/questions?prev=ppppp&sort=newest
https://stackoverflow.com/questions?next=nnnnn&sort=newest
Where "ppppp" and "nnnnn" represent the question numbers of the first and last questions, respectively, displayed on the current screen.
Clicking on the "next" link with the proposed change in place would make the first question at the top of the resulting page be the one that follows the last question (nnnnn) on the previously current page in reverse-date order.
Clicking on the "previous" link would make the last question at the bottom of the resulting page be the one that preceded the first question (ppppp) on the previously current page in reverse-date order.
The page-number navigation should probably remain as-is, otherwise you might wind up with negative page numbers. However, fast-forward and rewind links (<< and >>) with jump sizes of five or ten times the page length as well as begin and end links (|< and >|) could be added.
Having this feature would prevent your current view from scrolling out from under you as new questions are being added. Many forums and blogs use this form of navigation and I find it much more manageable when dealing with large numbers of entries on an active site.
Here is a mockup. I've separated the absolute navigation from the relative navigation to provide a clue that their behavior is different.
This is not a duplicate of this question.
Edit: added outlines to navigation buttons
