Community Tip - Did you get called away in the middle of writing a post? Don't worry you can find your unfinished post later in the Drafts section of your profile page. X
Bjarne is correct. I have seen this too, sometimes Pro/E retains odd relationships between parts which have nothing to do with each other anymore. I believe the path is Reference View under Tools. You should see a red "X" beside old references which can be broken.
You may also want to set the config.pro option "remember_replaced_components" to "no". This will uncheck by default the "remember these components" checkbox in the replace dialog box. It is that checkbox which creates the undesired reference - some kind of internal interchange assembly for replaced components.
The config option availablility depends on build code WF4 M120 or later.