There appears to be this bug lingering around since August 2006 that I did not fully look into today. A site that is hosted outside of the US, let's say, in the UK or Australia, with .com TLDs, are indexed in Google.com but are not in the index for Google.co.uk or Google.com.au, respectively.
A WebmasterWorld thread has been reporting sporadic issues of this since August and it has sprung up again around New Years. I travelled over to a recent Google Groups thread to get more evidence and examples.
The site http://www.awkspcrepairs.com/ is hosted in the UK (confirmed via traceroute). A site command search on the domain name in Google.com brings back the home page result (screen capture. A site command search on the domain name in Google.co.uk brings back the home page results (screen shot). But a site command search on the domain name in Google.co.uk with pages from the UK only does not return the index page of the site (screen shot).
That seems to be the issue. An other example was emailed to me by Nikhil, who told me to try a search on Telstra at Google.com.au and you will see www.telstra.com listed as number one, reportedly a Aussi site. But when you select the pages from Australia option, the main domain does not show up (screen shot).
Forum discussion at Google Groups and at WebmasterWorld.
