Self Tracking Entities - AcceptChanges cannot continue because the object's key values conflict with another object in the ObjectStateManager

I've been stuck with this problem for over a week now. Hopefully some one can point me in the right direction.

I start with a brief description of my schema.

Asset 1--->1 Address *-->1 Area *-->1 Region *-->1 Country

Package 1-->* Asset

Using Self Tracking Entity (STE) + WCF.

Steps:

1. Call data store for a list of assets.
2. Call data store for a list of packages.
3. User selects a package and assign some assets to it.
4. Save package.

In step 2, the call uses eager loading of Addresses.

from p in context.Assets.Include("Address.Area.Region.Country")

This is the error when attempting to call

context.Packages.ApplyChanges(package)

AcceptChanges cannot continue because the object's key values conflict with another object in the ObjectStateManager. Make sure that the key values are unique before calling AcceptChanges.

EDIT

After snooping around, i found that this is a STE issue. The problem being you cannot persist a graph that contains multiple instances of the same entity as outlined here. Here is my question.

How can I add an entity to my entity collection. The new entity may have related entities that contain the same key as one already in the collection. I.e. Add a new asset that may contain the same address, area, region or country entity.

Here are my constrains:

1. I must use the navigational collection because it affect the UI.
2. I cannot pre-fetch all entities that will be involved because the data set is simply too large.
3. I must be able to take snap-shots of the entity at anytime in order to keep a history and use it to "undo" any changes.

I am aware of the possible solutions suggested by Diego B Vega, but those are not options i can use for my solution. Has anyone any other ideas?

FYI, I wrote a blog post with some additional suggestions to what I had already responded in the EF Forums. Here is the blog post.