Dave Megginson has posted some questions about his understanding of REST.
First off, please do look beyond the "there are only 4 [HTTP] verbs" aspect of REST. "Hypermedia as the engine of application state" is hand-in-hand with Constrained Interface as being fundamental to the RESTful web. As well, the GET/POST distinction is critically more important than any other aspect of constrained interface, I believe.
Back to question 1 ... yes, the identifier does need to be recorded. This is the client's responsibility, though a good server would help. That is: if the usage of the protocol is embracing REST, then each message would already come back with the identifier of the resource baked in. In any case, I think there's a fallacy that the resource representation alone is or should be solely sufficient to describe the resource ... if that was the case, why does HTTP need headers at all!? Certainly, there is meta-data that the client must be responsible for.
On the client side, I think your options are: keep the data external to the representation, or keep it within the representation. Since you're assuming XML documents, I recommend that you use it's extensibility, maybe via a namespaced attribute on the root level. How about thisDocumentWasHttpRetreived:from="http://.../", or maybe rdf:about?. I've also used [eg:]href, which works well; you may like xlink:href, though.
Regarding identifiers and locations ... it's nice to know the identitiy of things; it's also nice to have locations of things. But it's really nice when your Uniform Resource {Identification,Location} scheme supports redirection, such as HTTP[s] does.