Actually the links aren't the problem, as you point out Ctrl+A+F9 takes care of the links.
What gets 'messed up' when adding a paragraph is the bookmark to were the link was pointing.
So the link may be pointing to the right bookmark, but now the bookmark got displaced for the added paragraph.
For instance, I got a table and immediately a heading after it which I have bookmarked and somewhere else I have a link pointing to it.
When I copy & paste the para tag as suggested, a paragraph is added between the table and the heading, but now if you click on the link it will take you to the new paragraph and not the heading; even after updating all the links in the document.
By the way, the c&p the para tag it's a pretty nifty solution in itself. Solves one mystery.