Returning 404 is correct according to http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html#sec10.4.4
"This status code is commonly used when the server does not wish to reveal exactly why the request has been refused" but will cause extra load on the web site and traffic, thus HEAD should be supported.
I stumbled over this issue while checking for dead links with gURLchecker. I wonder if this has some impacts on SEO visibility.