I am having the same issue, and, indeed, it is the <guid> that is causing the problem. In my case, Yahoo! and Reuters feeds (among others I'm sure) use relative paths, as washingtonpost.com and others use absolute. The thing that I have noted, however, is that the feeds that use relative paths for the guid seem to have an 'isPermaLink' attribute set to 'false' on the guid tag, while the absolute have the attribute set to true. I'm sure we can hack something together from that, right?
A couple of examples.........
from washingtonpost.com:
<guid isPermaLink="true">
http://www.washingtonpost.com/wp-dyn/content/article/2005/09/16/AR2005091600230.html?nav=rss_world
</guid>
from yahoo.com:
<guid isPermaLink="false">ap/20050916/un_summit_israel</guid>
Hope that helps