We do this (your requested) behavior for all our paginated web UI's. (I have actually asked for that in SO, and had it declined - but I find the current repagination annoying and unexpected - I hate hitting "next" and having the first n items be the last ones from the previous page).
The trick is to retain (usually in hidden variables) sufficient key information to position the list immediately before item 1 and immediately after the last item for the page you are looking at. Then your previous and next page links supply that information to on submit. Effectively you retain a "previous page" and "next page" key. This works intuitively for insertions and deletions.
One thing to bear in mind is that a refresh on page 1 (assuming like SO a newest items first list) should either (a) activate the "previous" link, if it was hidden, or (b) refresh the list from the top, including the added items. In other words "refresh" always redisplays the page from the first item inclusively, but if the first item on the page was also the first item in the list and now there are new items, it redisplays from the beginning of the list. With our lists we usually have, standard, links for "first page", "previous page", "refresh", "next page" and "last page".
The alternative for seeing new items is to always have a previous link and it backs up the smaller of a full page or the top of the list - and that's how a user sees new items (but I prefer to hide/disable the previous/next when there's no items previous and/or next).