The device ID is not necessary for such a query to be successful, though. If you as the device programmer were interested in getting the subset of the cache for your location, the method signature would need be nothing more complicated than:
So even in the "worst" case described by you no identifying data is sent. This could possibly be statistically analyzed, but given Apple's flat denials, a plausible technical reason, and the public attention this has received, I doubt they are lying here. A whistleblower providing evidence contradicting their "we don't track" claims would be devastating, and possibly open them up to legal action. I don't think they are quite that careless, although it is certainly possible.
The "flat denial" is in response to Apple's ability to "locate me" not "locate my iPhone." Elsewhere, Apple is very specifically making claims about the iPhone.
"Anonymous" is pretty slippery and there is no agreed upon technical definition (just ask EFF), but it literally means "not identified by name" so one could argue that sending tracking data based on your device serial number, IP address, phone number, location, contacts list, etc. is still in an "anonymous form." [somewhat similar to debates about the technical meaning of "open"].
I'll add that the information you are proposing to send to Apple is enough to clearly identify your location - or rather the location of the iPhone, and short of Apple using Tor or a similar approach to making the message's route through the network untraceable, the data in "anonymous form" can likely be disanonymized.
