I am not sure what you mean by your opening line:
NB: I'm assuming a REST service that uses URIs to identify resources, I'm aware this isn't strictly a constraint of REST
do you mean that hyperlinks don't have to be URIs? or that hyperlinks don't have to point to resources? The former is technically true but on the internet, URIs are the only form of hyperlink, so unless you're thinking about something Completly Different, then they are URIs. If you are saying REST doesn't require that URIs identify resources, then this is just wrong. That's exactly what they identify in a RESTful API. Always.
Anyway, onward to your question:
Does this mean the client can only use URIs given to it by the latest request, or can the client keep track of URIs received in earlier requests from the same session?
Yes, a client can cache previous responses. If they are 'fresh' (per the Expires or max-age headers) then the client can use them immediatly. If they are 'stale' (max-age/Expiry time exceeded) then the client MAY re-request the resource using a conditional request (e.g. If-Modified-Since), but it doesn't have to.
Neither of your examples constitute a REST violation. On the contrary, they are both wonderful examples of the simplicity of the system!