This seems like a phishing attack, and it's a disclosure vulnerability to send 404 response in this case. Unfortunately that's just what IIS does.
I would rather these guys not even know my server existed.
Edit: Of course, once a TCP connection has already been established, they know something is on that port. It might be nice if they didn't know it was IIS on the other side
When you say "random domains" you mean hostnames right? Not IP addresses?
If the former, a hostname is, at least in theory, completely disconnected from the actual IP address of the server from the point of view of the server. Every (well, almost every) HTTP request will have a HTTP-Header called 'Host', it's very easy to simulate or "fake" it. Take the following command
(Ignore the output)
That command gets Google's servers to respond to a request for 'serverfault.com' as if it was a normal virtual host, which in the case of Google looks like it's pointing to a file that redirects to the main Google site.
Put simply, there is no way to 'block' these requests without getting your firewall to analize each request and that opens up a whole other world of issues. A 404 or 403 response is correct, 404 means the resource does not exist on the server, although normally this reffers to a file, it could reffer to an entire site too.
Your server choosing to respond or not, is based (simplisticly) solely on the target IP address, not the hostname. By the time the server gets to reading the hostname it's already established a connection. Yes you could get it to just drop the connection but responding with a 404 is a much better option because it officially tells the client the resource does not exist.