This is very dependent upon the configuration of the relationships. See Entity Framework .Remove() vs. .DeleteObject()
Since your relationship sounds to be a many to many, you will likely need to call DeleteObject for the addresses themselves, as EF won't automatically delete the orphaned records.