You actually don't need to honour the links.

If a client gets a 410 when following a stored link, they can always find the new url for the resource by following links from the parent resource (this is recursive, all the way back to the root url).