Can somebody explain how the check.tp.o query works, for normal users, so its clear why this happens?
check.tp.o is composed of two parts, TorDNSEL and TorCheck. TorDNSEL is used to create a list of all the IPs that correspond to exit relays. That is, when you exit from a relay, what IP do you assume. It does this by running an http server listening on a few ports and building various circuits through the relays back to itself. This is done every hour, after a new consensus is reached in the Tor network and currently takes about 20 minutes to complete. The list is then fed to TorCheck, where it's combined with the current consensus and exit policies of the relays, to create a map of all the IPs that can exit to check.tp.o on port 443 from the Tor network. When you launch the TorBrowserBundle (and hit Test Network Settings in the 3.x series), TorCheck compares the remote address of the request it receives to its map and returns True if it finds it there.
In particular, what are all the cases that can lead to false negatives? I think the two big ones are "the exit relay makes outbound connections from a different IP address than it lists in the directory, and the Tordnsel tester hasn't caught it yet or otherwise has a bug" and "that exit relay only came up recently so check doesn't know about it yet".
The cases I know about are:
For one, TorDNSEL is not currently listening on port 443 so certain restrictive exit policies won't let it learn the exit address while still permitting requests to check.tp.o
A new consensus in the Tor network is reached every hour. The tor client, however, keeps a cache of the consensus around for a while. Over time, relays fluctuate in and out of the consensus as they go offline, reboot or whathaveyou. If a relay that used to be part of the consensus (and is thus in a clients cache) comes back online, a client may exit from it before the hour, when the new consensus is reached, and TorCheck won't know about it yet. In an attempt to mitigate this scenario, TorCheck keeps a map of all the IPs from the past 16 hours. There's a tradeoff here between false positives and negatives.
Some relays see a lot of churn in their IPs throughout the day. TorCheck tries to keep track of all the IPs it has seen from a given relay over time. Again, this can result in more false positives and isn't guaranteed to catch a new IP before the hour.
There's certainly a lag between the time that the new consensus is reached (on the hour) and when TorCheck is updated. As stated above, TorDNSEL continues to update its exit list until 20 minutes past the hour. There's still a timing issue to be worked out here and it's possible that TorCheck doesn't have the right IP for up to an hour after a new relay enters the consensus.
Bugs in both TorDNSEL and TorCheck are always a posibility.
When users encounter one of these false negatives, should they use a separate "IP check" website like ipchicken.com to check/verify?
It may be better to click on TorButton and create a New Identity, and then hit check.tp.o again.
Why did TBB 3.0 switch to using a local homepage instead of using Tor Check? What are the benefits?
For one, it's not a great idea to have the entire userbase hitting a single website to learn "tor or not" every time they launch their browser. Certainly the website has had scalability issues in the past and will only continue to do so as the userbase grows. More importantly, however, is that it probably isn't wise to rely on a hostile network for confidence that you are in fact using tor properly.
