This may have been the first thing you did but have you confirmed that the RELATED TO is actually based on the Related table and not the Contacts table by mistake?
Re: "Neither relationship is set to delete related records" the behaviour you describe certainly sounds like this is the cause, even though you say it isn't.
In addition to Todd's suggestion, you should carefully check that the "delete related" option is not checked by mistake; it sounds as if it might be checked to delete the CONTACT record when the RELATED record is deleted.
Another possibility: is RELATED merely a join table? If so, make sure it is set up correctly as its own separate table, and that the relationships it uses are both unchecked in both directions.
In another forum it was pointed out to me that the setting "Delete related records in this table when a record is deleted in the other table" is not context sensitive. So although the portal I was deleting in did not have this set, it was set somewhere else in the graph.
Thanks for your help.