OK, I think I got it now.
First, I'm not fussing with any of the Diagram Property settings, I think they are all set to default settings. But, in this testing scenario the "Show Relationships" checkbox is checked on the diagram properties window.
To recreate, 1) create a diagram and place two new objects on it, Object1 and Object2. 2) Create an association between the two. I created a dependancy link but I doubt it matters.
If you select the link and press the delete key, OR select the link, right click and from the pop-up select Set Visibility->Hide Connector then you CAN go to either object's link tab, right click on the relationship and select "Show Relationship" and it is visible again in the diagram.
HOWEVER, if you select the connector, right click and then select Delete at the bottom of the pop-up menu I have yet to figure out how to show the relationship again. If you go to the link tab of either object, for some reason the "Show Relationship" option is not available when you right click on the link of interest.
We're using 6.5 build 799.
BTW, I have set my pref so that when I delete an item from the diagram, it simply hides it and doesn't delete it from the model; On the "Remove Connector" dialog box I've checked the box that says, "Don't ask again" and Hide the Connector.
Hope that's much clearer.