Using the new XWPFParagraph.createHyperlinkRun method (from https://github.com/apache/poi/pull/153), I noticed that some links do not have a valid rId: at some point, I got "rI1", which was already used in the relations. 

In more details: I was trying to add a link inside a footnote. This run was generated in footnotes.xml: 

<w:hyperlink r:id="rId1"><w:r><w:rPr><w:color w:val="0563c1"/><w:u w:val="single"/></w:rPr><w:t>avec bien plus de lourdeur</w:t></w:r></w:hyperlink>

However, neither in footnotes.xml.rels nor in document.xml.rels could I find the link I just added. The worse was in document.xml.rels, where this ID already existed: 

<Relationship Id="rId1" Target="numbering.xml" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/numbering"/>

In my case, the solution was not to get the ID from getPart(), but from getDocument(). I ended up with this code: 

String rId = paragraph.getLast().getDocument().getPackagePart().addExternalRelationship(
                    uri, XWPFRelation.HYPERLINK.getRelation()
).getId();

Thus, I think that the code of XWPFParagraph.createHyperlinkRun should be changed to: 

    public XWPFHyperlinkRun createHyperlinkRun(String uri) {
        // Create a relationship ID for this link. 
        String rId = getDocument().getPackagePart().addExternalRelationship(
                uri, XWPFRelation.HYPERLINK.getRelation()
        ).getId();

        // Create the run. 
        CTHyperlink ctHyperLink = getCTP().addNewHyperlink();
        ctHyperLink.setId(rId);
        ctHyperLink.addNewR();

        // Append this run to the paragraph. 
        XWPFHyperlinkRun link = new XWPFHyperlinkRun(ctHyperLink, ctHyperLink.getRArray(0), this);
        runs.add(link);
        iruns.add(link);
        return link;
    }

As I am really unsure about this, I prefer to open an issue rather than create a pull request…