I did some logging of the requests from Facebook, I've found out some more info. They appear to have two servers that do the external requests, 69.63.178.250 that executes requests successfully from www.neonsleep.com, and 69.63.178.247 which always fails with the error above. I dumped the contents of $_REQUEST and $_SERVER, and the servers differ slightly in their requests:
.250 (the working server), sends requests like:
$_REQUEST['url'] = /doilookthin/30
$_SERVER[REDIRECT_STATUS] = 200
$_SERVER[HTTP_USER_AGENT] = facebookexternalhit/1.0 (+http://www.facebook.com/externalhit_uatext.php)
$_SERVER[HTTP_ACCEPT_ENCODING] = gzip
$_SERVER[HTTP_HOST] = www.neonsleep.com
$_SERVER[HTTP_ACCEPT] = text/html, image/gif, image/jpeg, *; q=.2, */*; q=.2
$_SERVER[HTTP_CONNECTION] = keep-alive
$_SERVER[CONTENT_TYPE] = application/x-www-form-urlencoded
$_SERVER[PATH] = /usr/local/apache_php5/sbin:/usr/bin:/bin
$_SERVER[SERVER_SIGNATURE] =
$_SERVER[SERVER_SOFTWARE] = Apache/2.2.4 (Unix) mod_ssl/2.2.4 OpenSSL/0.9.8c PHP/5.2.4
$_SERVER[SERVER_NAME] = www.neonsleep.com
$_SERVER[SERVER_ADDR] = 60.234.4.41
$_SERVER[SERVER_PORT] = 80
$_SERVER[REMOTE_ADDR] = 69.63.178.250
$_SERVER[DOCUMENT_ROOT] = /www/virtual/neonsleep.com/htdocs
$_SERVER[SERVER_ADMIN] = webmaster@neonsleep.com
$_SERVER[SCRIPT_FILENAME] = /www/virtual/neonsleep.com/htdocs/sapphire/main.php
$_SERVER[REMOTE_PORT] = 36769
$_SERVER[REDIRECT_QUERY_STRING] = url=/doilookthin/30
$_SERVER[REDIRECT_URL] = /doilookthin/30
$_SERVER[GATEWAY_INTERFACE] = CGI/1.1
$_SERVER[SERVER_PROTOCOL] = HTTP/1.1
$_SERVER[REQUEST_METHOD] = GET
$_SERVER[QUERY_STRING] = url=/doilookthin/30
$_SERVER[REQUEST_URI] = /doilookthin/30
$_SERVER[SCRIPT_NAME] = /sapphire/main.php
$_SERVER[REQUEST_TIME] = 1236809221
$_SERVER[argv] = Array
$_SERVER[argc] = 1
.247 (the non-working server), sends requests like:
$_REQUEST['url'] = /doilookthin/20
$_SERVER[REDIRECT_UNIQUE_ID] = HNk2xKwQZC0AADLIgbQAAABF
$_SERVER[REDIRECT_STATUS] = 200
$_SERVER[UNIQUE_ID] = HNk2xKwQZC0AADLIgbQAAABF
$_SERVER[HTTP_USER_AGENT] = facebookexternalhit/1.0 (+http://www.facebook.com/externalhit_uatext.php)
$_SERVER[HTTP_ACCEPT_ENCODING] = gzip
$_SERVER[HTTP_HOST] = www.neonsleep.com
$_SERVER[HTTP_ACCEPT] = text/html, image/gif, image/jpeg, *; q=.2, */*; q=.2
$_SERVER[HTTP_CONNECTION] = keep-alive
$_SERVER[CONTENT_TYPE] = application/x-www-form-urlencoded
$_SERVER[PATH] = /usr/local/bin:/usr/bin:/bin
$_SERVER[SERVER_SIGNATURE] = <address>Apache/2.2.3 (Debian) PHP/4.4.7 mod_ssl/2.2.3 OpenSSL/0.9.8c Server at www.neonsleep.com Port 80</address>
$_SERVER[SERVER_SOFTWARE] = Apache/2.2.3 (Debian) PHP/4.4.7 mod_ssl/2.2.3 OpenSSL/0.9.8c
$_SERVER[SERVER_NAME] = www.neonsleep.com
$_SERVER[SERVER_ADDR] = 219.88.240.130
$_SERVER[SERVER_PORT] = 80
$_SERVER[REMOTE_ADDR] = 69.63.178.247
$_SERVER[DOCUMENT_ROOT] = /www/virtual/neonsleep.com/htdocs
$_SERVER[SERVER_ADMIN] = webmaster@neonsleep.com
$_SERVER[SCRIPT_FILENAME] = /www/virtual/neonsleep.com/htdocs/sapphire/main.php
$_SERVER[REMOTE_PORT] = 43559
$_SERVER[REDIRECT_QUERY_STRING] = url=/doilookthin/20
$_SERVER[REDIRECT_URL] = /doilookthin/20
$_SERVER[GATEWAY_INTERFACE] = CGI/1.1
$_SERVER[SERVER_PROTOCOL] = HTTP/1.1
$_SERVER[REQUEST_METHOD] = GET
$_SERVER[QUERY_STRING] = url=/doilookthin/20
$_SERVER[REQUEST_URI] = /doilookthin/20
$_SERVER[SCRIPT_NAME] = /sapphire/main.php
$_SERVER[PATH_TRANSLATED] = /www/virtual/neonsleep.com/htdocs/sapphire/main.php
$_SERVER[argv] = Array
$_SERVER[argc] = 1
I've tried contacting Facebook for help, but of course it's impossible to get any support out of a business that large.