What’s the most appropriate HTTP status code for an “item not found” error page

HTTP PUT:

PUT puts a file or resource at a specific URI, and exactly at that URI. If there's already a file or resource at that URI, PUT replaces that file or resource. If there is no file or resource there, PUT creates one. PUT is idempotent, but paradoxically PUT responses are not cacheable.

HTTP 1.1 RFC location for PUT

HTTP POST:

POST sends data to a specific URI and expects the resource at that URI to handle the request. The web server at this point can determine what to do with the data in the context of the specified resource. The POST method is not idempotent, however POST responses are cacheable so long as the server sets the appropriate Cache-Control and Expires headers.

The official HTTP RFC specifies POST to be:

• Annotation of existing resources;
• Posting a message to a bulletin board, newsgroup, mailing list, or similar group of articles;
• Providing a block of data, such as the result of submitting a form, to a data-handling process;
• Extending a database through an append operation.

HTTP 1.1 RFC location for POST

Difference between POST and PUT:

The RFC itself explains the core difference:

The fundamental difference between the POST and PUT requests is reflected in the different meaning of the Request-URI. The URI in a POST request identifies the resource that will handle the enclosed entity. That resource might be a data-accepting process, a gateway to some other protocol, or a separate entity that accepts annotations. In contrast, the URI in a PUT request identifies the entity enclosed with the request -- the user agent knows what URI is intended and the server MUST NOT attempt to apply the request to some other resource. If the server desires that the request be applied to a different URI, it MUST send a 301 (Moved Permanently) response; the user agent MAY then make its own decision regarding whether or not to redirect the request.

Additionally, and a bit more concisely, RFC 7231 Section 4.3.4 PUT states (emphasis added),

4.3.4. PUT

The PUT method requests that the state of the target resource be created or replaced with the state defined by the representation enclosed in the request message payload.

Using the right method, unrelated aside:

One benefit of REST ROA vs SOAP is that when using HTTP REST ROA, it encourages the proper usage of the HTTP verbs/methods. So for example you would only use PUT when you want to create a resource at that exact location. And you would never use GET to create or modify a resource.

If "validation failure" means that there is some client error in the request, then use HTTP 400 (Bad Request). For instance if the URI is supposed to have an ISO-8601 date and you find that it's in the wrong format or refers to February 31st, then you would return an HTTP 400. Ditto if you expect well-formed XML in an entity body and it fails to parse.

(1/2016): Over the last five years WebDAV's more specific HTTP 422 (Unprocessable Entity) has become a very reasonable alternative to HTTP 400. See for instance its use in JSON API. But do note that HTTP 422 has not made it into HTTP 1.1, RFC-7231.

Richardson and Ruby's RESTful Web Services contains a very helpful appendix on when to use the various HTTP response codes. They say:

400 (“Bad Request”)
Importance: High.
This is the generic client-side error status, used when no other 4xx error code is appropriate. It’s commonly used when the client submits a representation along with a PUT or POST request, and the representation is in the right format, but it doesn’t make any sense. (p. 381)

and:

401 (“Unauthorized”)
Importance: High.
The client tried to operate on a protected resource without providing the proper authentication credentials. It may have provided the wrong credentials, or none at all. The credentials may be a username and password, an API key, or an authentication token—whatever the service in question is expecting. It’s common for a client to make a request for a URI and accept a 401 just so it knows what kind of credentials to send and in what format. [...]