In cases where a question was deleted, a 404 response is not technically accurate, especially when the body of the response indicates:
This question was removed from Stack Overflow for reasons of moderation.
Content that used to exist but doesn't anymore is gone, especially if the server knows what content the user is looking for but knows it's gone.
With recent concerns raised about external link rot regarding popular deleted questions, one way to help external link checking agents deal with this would be to use a proper response code. This doesn't apply so much to questions that are not sufficiently popular or meaningful, but more for the ones that have external links.
I propose that for deleted questions with more than 3 up-votes or older than 60 days, the response code should be 410, not 404.
Also, as a final point of support, abiding by the HTTP spec as much as is reasonable seems to be about as closely aligned as possible to the mission of Making the Internet a Better Place.
Note: I tagged this as bug instead of feature-request since, according to the HTTP spec 410 Gone is the correct response code
gone
?