The latest version of Quick Cache, v140605.1, includes a new feature called 404 Caching, which is disabled by default. With this option disabled, your 404 pages will not be cached.
New Feature: 404 Page caching. It's now possible to enable/disable the caching of 404 requests. Enabling this feature generates a single cache file for your 404 Page and then symlinks future 404 requests to that cache file. See Dashboard -> Quick Cache -> Plugin Options -> 404 Requests.
That said, upon reviewing this support thread after publishing the new version, I realized that the bug you mentioned may still exist when 404 Caching is enabled. Sure enough, it does. I opened a new bug report here related to this new feature and will get this bug fixed for the next release which will happen within the next few weeks. Until then, you may want to leave the 404 Caching option disabled.
I'm going to leave this support thread open for now and close it after the bug is fixed.
Again, for now, you can simply update to v140605.1 and leave the 404 Caching option disabled. With that option disabled, WordPress will return the proper 404 status code.