I've noticed consistent false positives on certain redirect links, and I think I've finally isolated the cause. The links in question are returning a URL with an in-page anchor at the end, of the form http://example.com/page1#section1, and the anchor is not being removed before checking the new location. So it sends the whole thing, asking the server for a file named "/page1#section1", which doesn't exist, generating a 404 error.
An example: http://tr.im/avgi
1. Log : === First try : 404 ===
HTTP/1.1 301 Moved Permanently
Date: Tue, 17 Feb 2009 03:37:03 GMT
Server: Apache/2.2.9 (Ubuntu) PHP/5.2.6-2ubuntu4 with Suhosin-Patch Phusion_Passenger/2.0.6
X-Powered-By: Phusion Passenger (mod_rails/mod_rack) 2.0.6
Set-Cookie: _trim=7c626ad8db30c14a82232fc8b99e16d2; path=/; expires=Mon, 18 May 2009 01:28:08 GMT
Content-Type: text/html; charset=utf-8
Trying a second time with different settings...
=== Second try : 404 ===
HTTP/1.1 404 Not Found
Date: Tue, 17 Feb 2009 03:28:21 GMT
Server: Apache/2.2.3 (CentOS)
Expires: Wed, 11 Jan 1984 05:00:00 GMT
Last-Modified: Tue, 17 Feb 2009 03:28:21 GMT
Cache-Control: no-cache, must-revalidate, max-age=0
Content-Type: text/html; charset=UTF-8
Link is broken.