http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf

Doh! Just noticed you already are aware of that particular work. Anyway, congrats, you're already aware of the state of the art!

There are techniques to do this but none have made it out of academia. Most are quite inefficient and support very restricted querying models. Here's one paper that claims their methods are "practical" (but always keep in mind that academic claims of practicality should always be taken with a grain of salt):

http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf

The purpose of the ID is described here. But you may need to take off the tin foil hat before you can understand it.

GoogleUpdate also uses its own, randomly-generated unique ID number to accurately count total users. This information includes version numbers, languages, operating system, and other install or update-related details, such as whether or not the applications have been run. This information is not associated with you or your Google Account.

FAST ?! You mean that company that was a front for a bunch of norwegian scammers that tricked MS into buying it? Also known as the "Enron of Norway"? Surely you jest.

Wow, someone actually read the article! The article is not about the outcomes of the various cases discussed, but the tactics that are being used. It's a good read.