Your workflow is a recipe for disaster. While InDesign tends to be quite stable, continued "recycling" of exiting files can cause long term cumulative build-up of minor corruption that eventually leads to failure.
A newspaper should be based on template file that contains master pages for various page configurations, any static content, and all of the required styles. Each issue should be a fresh document based on the template. You can probably safely copy and paste continuing content like ads from issue to issue, but I prefer to place them fresh.
That aside, see Remove minor corruption by exporting. It might clear up the links problem.
Adding to Peter's excellent comments, you might like know that Lynda.com has an excellent new online tutorial on creating InDesign templates : http://www.lynda.com/InDesign-tutorials/Designing-Templates-InDesign/374188-2.html
(I have no connection with Lynda.com.)
Thank you for your quick reply and good advice!
I did create a new fresh document, copied all the pages one by one from the old one, and now it works just fine!