As you will see if you run your pptx through PartsList, slides are referenced in presentation.xml
Using xml Syntax Highlighting
<p:sldId id="256" r:id="rId2"/>
<p:sldId id="257" r:id="rId3"/>
Parsed in 0.001 seconds, using GeSHi
so you need to remove the relevant p:sldId entry, and the corresponding relationship from MainPresentationPart's relationship part.
Part /ppt/presentation.xml is class org.docx4j.openpackaging.parts.PresentationML.MainPresentationPart containing JaxbElement org.pptx4j.pml.Presentation
The removePart method works recursively, which is probably what you want for a docx, but isn't for a pptx (since slides reference a layout which in turn references a master, which then references all layouts, and you won't want to delete all of them).
So instead, use the lower level removeRelationship method, and remove the actual part, as you have done.
So, in outline:
Using java Syntax Highlighting
MainPresentationPart presentation =
// First, delete the slide
SldIdLst sldIdLst =
// .. etc
// Second, delete the rel
RelationshipsPart rels =
rels.removeRelationship // etc
// Also, delete the specified part from the package.
Parsed in 0.045 seconds, using GeSHi