I created an issue for this https://tracker.moodle.org/browse/MDL-50808 but as a brief summary.
If an LTI link is created in a version previous to Moodle 2.8 (lets say 2.5) configured to receive grades and used, the reference to the gradebook created at that point does not work if the server is upgraded.
When using the reference (lis_resource_sourcedid) stored by the Tool Provider, Moodle responds with a 404 error.
There should be backward compatibility, and my guess is that the bug is in the form the sourcedId is validated when the replaceResult request is received, but it may also be in the reference to the item in the gradebook, so the script for upgrading would be the culpit (this I don't know, I am not that familiar with the internal code).
Anyways, the workaround found is to ask students to use the link again. that seems to be rebuilding the reference along with the new ID used as lis_result_sourcedid.