Given that it's IIS, adding
<% Response.Status = "404 Not Found" %>
to the top of 404.shtml should change the response code to 404.
I am not on a windows machine so I am unable to test it at the moment to verify.
Update:
I was finally able to run a few tests on a IIS 6. As you mentioned in a comment to my post, an .shtml file does not allow script commands to run. So there are at least two ways to work around this:
Instead of naming your custom 404 handling page 404.shtml, name it 404.asp. The user should never see the actual name of the page so it shouldn't cause any issues. Note that "Active Server Pages" must be set to 'Allowed' in the Web Service Extensions folder of IIS.
Modify the page extension mapping for .shtml to use asp.dll instead of ssinc.dll. You can do this from IIS by selecting the website and viewing Properties -> Home Directory tab -> Configuration -> Mappings tab. Note that this is far from an ideal solution because now all your .shtml files will be processed by asp.dll. This could cause your pages to render more slowly (assuming asp.dll processes files more slowly than ssinc.dll due to greater complexity) and violates the principle of least privilege.
If neither of the options fit your situation, then it may still be possible but the solution isn't immediately obvious to me.