There are some behavior differences you should be aware of that may help you.
After a relaunch of my site and after a period of 301 redirects to new pages, I decided to issue 404 errors but recapture the traffic that might have gotten lost with custom HTML. The 404 page worked as expected, however, when I dropped the custom 404 HTML, I found 2 of my pages returned a 404 but also return HTML content (soft) and remained indexed. If these pages simply returned a 404 without HTML at all (hard), Google would take note.
There are in effect 2 soft 404 pages. One is to issue the 404 in code and the other is to actually create a custom page that the web server issues. Using code, while the 404 header may be issued correctly, if you issue HTML with it, Google may not take it too seriously. This may be on a language by language basis. Yes. You get a 404, but it seems Google can treat it differently. When possible, it is far better to let the web server and not a CMS to issue the 404.
There does seem to be a difference in how 404 is handled in how Google handles the 404. I have yet to correct these two pages and I still get search results from Google and yet, I give a proper 404 response. It is on my list to fix of course- I am just a bit slow.
When a page does not exist, the easiest thing to do is allow it to 404 naturally using the web server without HTML. This is the default for any web server. However, some CMS are set-up to give a soft 404. The reason for this is to recapture traffic that would otherwise would be lost. Google does not like soft 404's for a reason, but does understand that they have value. Google does prefer a hard 404.
It is technically correct to offer a 410 for any page that is gone. Google treats a 404 and 410 differently. Any page that returns a 410 is delisted from the index immediately and not requested again (generally), while a 404 is thought to be a temporary scenario and Google will retry the page a number times before delisting the page from the index.
Keep in mind, as long as there are links, these pages may be retried periodically. That would make sense of course, but this is how it works. If Google follows a link and delists the page from the index because it is not there, Google marks the link as a dead link (dangling- their term). Google generally will not retry the link again after a number of 410 or 404 errors. However, if a new link appears, the Google starts the process all over again for the new link.
As long as you return a 410 or a 404 and no HTML, all will be fine. However, if you can issue a 410 for the page, then that would be best. It certainly would be less annoying and help to delist these pages more quickly.