I know this is an old question, but I think there's a subcomponent to the answers that I see here that hasn't been addressed.
Remember that you're not retrieving the resource from the server, but you're retrieving a REPRESENTATION of a resource. The resource itself may have its primary identifier change, or be rehomed, or whatever, but the representation that was returned to the client on resource creation may (or may not be) valid independently; it's all a matter of situation.
As an example, consider a moderated content upload system; a user may have the ability to upload content for consideration by the moderators that may eventually cause the content to be exposed to a wider audience / market. On initial upload, the server may respond with a URI that directs to (say) "users/{userid}/uploaded/{contentid}" for that representation of that content. At some point, the moderators may decide to promote the content to a "front page"; that representation of the content may then be available at the URI of "content/{contentid}"; that should not prevent the original uploader from accessing their data at "users/{userid}/uploaded/{contentid}"; nothing says that there needs to be a permanent redirect, and in fact, there's good reason for there not to be; if the user decides they want to remove the content, they should be able to perform a DELETE on the content; it's probably much preferential to have users doing DELETEs to the content representations from their own "uploaded" locations. However, if the terms of the site indicate that user rights to content uploaded are revoked (not uncommon) it might make sense to have the moderation promotion process effectively remove the content from the user's own area, causing a "permanent move".
It's really entirely dependent upon the specific situation; the validity of a cached URI is completely dependent upon the server's policies. At the least, I'd think that a request to an invalid URI (that may have previously been valid) should cause a response (consistent with HATEOAS) that can allow the client to "rediscover" the resource (representation) they were looking for; at the very least, a link to the entry-point.