We don't add any GUIDs. We just use them if they're present in source feeds. Since these are globally unique, we consider an item "done" based on its GUID. If the GUID changes, we recrawl it. We have to do this otherwise we'd be processing 80000+ feeds in full every few minutes :) Source feed items without GUIDs are tracked based on destination URL and title, but this only works if the GUID is actually not present.
The reason we switched to this system is because there were many feeds (mostly weather or horoscope related) where item titles and URLs never updated but the GUID did.. so we moved to using the GUID if present. This has had a lot of benefits, but naturally there are some downsides in situations like this.
In theory I can refresh feeds for you manually and have them recrawled from new, but this is not really an ongoing solution.
The "fix" for this problem is for us to have a "what's in the feed is what's in our database" system which doesn't do archiving, etc, but literally just replaces all content in our database with what's in the feed at the time. This would help in situations like this, but is not ready to roll as yet.