DOn't change your 404 to 410 - non-existant pages still need to return the proper 404 page with 404 headers to tell search engines a page really didn't/doesn't exist, like misspellings. 410 is generally for search engines only but I do use custom pages (with the proper headers) in case a live person shows up.
HTACCESS would work if there was something common about the pages like a directory/folder name or the page extensions (.html, .aspx).
Is it possible for you to restore those pages? They don't have to have real content but if you could somehow regenerate the pages you can make them all identical 410 pages (remember those headers).