Thinking about this some more, I think a lot of users are going to run into this issue and not understand what's going on. So I think the long term plan will be to start tracking deletions of all objects (songs, setlists, collections, etc), and possibly track renaming as well. This will add some unnecessary data to the database for users that don't rely on the synchronization functionality, but it should be a small amount that is barely noticeable in terms of the file size. I may also decide to purge entries from the history after they grow old enough (older than a month or two). I don't want to take on this work until after the annotations rework and iOS version though, so it won't be implemented until later this year.
Mike
Mike