In a scenario where a service model has already been published to the TrueSight Infrastructure Management Server, and subsequently a relationship in that model is removed using the 'remove' button in the Remedy Asset Management Console (not in the Impact Model Designer, Atrium Explorer, nor CMDB Console itself), that relationship is not unpublished from the TrueSight Infrastructure Management Server after a normal publish.
When the relationship is 'removed' via the Remedy Asset Management Console in midtier, that is a hard deletion being performed. Instead of just being Marked for Delete, it is completely removed from the BMC.ASSET dataset.
Therefore, to unpublish the relationship, you need to run a purge publish job on the TSIM Server with:
publish -p "Purge=T"
This should then remove any relationship and/or CI that was hard deleted.