Think of bookmarking as caching the URI. You cannot be sure that your cache contains the actual URI. You cannot keep that URI too long or you need to check if it is not 404. In the latter case you can try to rediscover it. I don't think rediscovering is always possible or worth the effort. E.g. if you find the URI by pagination and it was on the 1000th page, then the cost of rediscovering it is high unless you save the page number, which can change ofc... I think you need some sort of bookmark service for those cases. E.g. you can give the params you passed to the URI template and the resource type or you can give the old URI to that service and it should return the new URI. I don't know what is the ideal solution for this.
later:
Meanwhile I discussed this with REST experts, but we could not agree on the right solution. They proposed the sunset header or the deprecation header, but both tell the client that the resource will be removed. I think that is not the case here, because we keep the resource and only the URI changes, so in our case the resource will be moved. We have a 301 moved header for that and we can used redirection. I think after a while we can change that to 404 and add an error message that the URI changed. Later we can remove the path and return with 404 without explanation.