I have several 404 errors with a URL such as: myWebsite/tag/foo/page/4/. Page no longer exists because a few posts were deleted tagged as "foo." Which is better: 301 redirect that to myWebsite/tag/foo/page/1/? Or just 410 delete them?
I'm thinking if I do a 301 redirect -- then add more posts tagged as "foo," a 4th page will exist but those will be redirected back to page 1. Or if I 410 delete page 4 and it later exists in the future, it won't be found. I'm confused.
This is a tricky one.
The quick and dirty (but correct) solution is to use a 307 temporary redirect and then remove it when the page returns. This way your SEO will not suffer from the 404 errors and search engines will know that the page might come back.
However, if this is something that will happen often, it might be worth while looking at how the theme manages pagination and utilizing wp_redirect() to handle the redirect dynamically.
If you need help with the dynamic route please add a new question referencing your pagination setup.
I'd vote for a general-purpose 404 page, that says something like "That page doesn't exist, sorry." You could even provide a link to a search page.
That type of 404 redirect is easily done via your htaccess file
ErrorDocument 404 /my-404-page
which would redirect to http://www.example.com/my-404-page (an actual WP page that has that as a slug). Adjust as needed for your site.
But my solution doesn't take into account the effect on SEO for your site. And perhaps it would be better to look at your theme code to see why it is returning a page when there is no such page.
