Shepherd, does your site return a 404 under other circumstances, such as when there's a garbage request? That is, "example.com/akjkvljcufoidrtujd.html" and the like. Google itself makes requests in this form; it's probably automated but the trigger is pretty low. (That is: I've seen it myself, typically after I've made major changes.)
If yes, then we are getting into something interesting. It used to be that "soft 404" was a site-wide issue: they were only interested in sites that never returned a 404 at all, ever. Now they're getting more narrowly focused.
Do you-- or can you-- add a meta "noindex" to pages of this kind? Seems like they shouldn't react as strongly to a soft 404 if the result isn't intended to be indexed anyway.