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
curl -H "Host: serverfault.com" http://www.google.com/
(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.