I’ve got a situation where I am going to paginate listings in a directory, which means there may be any number of pages depending on the current row count in the database. If google comes by or a person has bookmarked one of these pages, but the page no longer exists, I’d like to either redirect (302?) or do a 404, but I’m not sure which, and I don’t know if there is a better HTTP status code. The page might be available again, so I especially don’t want Google to think it is Gone for good. What should I do?
For that scenario, I think 307 Temporary Redirect may be your best bet. http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html
I would do a 307 page to a page indicating something to the effect of “it might be back, not sure”.
However, it sounds like you’re talking about doing something like this:
/directory/cookies/3
where 3 would be the third page. And you are concerned if the number of entries drops so there are only 2 pages, 3 would be bad.
In that case, I would probably do a 301 Moved Permanently and redirect them to the last page in the listing.
Google and users won’t be happy if you keep giving them 302s and 307s. 
I think I would go with a 404, since the page is really gone, and for all you know it might be gone for good. If it ever comes back surely google will find it again. The main advantage of the 404 is that google will drop the result from the SERPs which IMHO is the correct thing to do because it’s not actually there.
This is the kind of thing that can cause google to return a result for your website when the page is in fact already gone. Very annoying.