TreeStore does this already, but only emits an error in Dev Mode*, to prevent the need to do an extra check every time that an item is added in production code.
ListStore currently only relies on that string in cases like Records and when the find methods are used to look up items. My proposal would be for ListStore to have a Dev-Mode-only* check for new items, either a Set<String> or a walk through the current list each time something is added. Does that seem reasonable?
I've made a few changes in ListStore so that whenever assertions are enabled (-ea flag when compiling, or by default in dev mode), all keys will be tracked and an exception will occur when adding a second model with the same key as an existing model. These changes are in SVN and will be available in the next release.