That's a fair perspective. I suspect my app installation habits differ from most users.

It seems that a good number of apps do this to "find friends" using the app. It would certainly be much better if upon app installation your associated account e-mail was hashed using SHA256 (or some alternative hashing algorithm) and stored by the service. Rather than upload a users entire contact list the apps could then submit hashes of contact e-mail addresses looking for matches without being able to identify users not using the service in question.

You are 100% right about the Android Device ID but is less of a privacy concern than the ESN, IMEI, etc that is protected by READ_PHONE_STATE. It is randomly generated, and can change with factory reset or by means of root access. The use of the Android Device ID for the purpose of tracking app installations is clearly supported behavior with the caveats I mention outlined.

Worry #1 is probably not that devastating a concern. The Google platform distribution shows only 0.3% of users are running 1.5 or below at this point. It is my experience that few apps support Cupcake and below.

I think it's worth noting that the new malicious applications found by McAfee researchers were video trailer applications that overtly requested the READ_PHONE_STATE and READ_CONTACTS permissions at install time.

While it's clear that users have limited comprehension of the permissions requested at install time (for instance see: Android Permissions: User Attention, Comprehension, and Behavior) it is rather suspicious that a trailer application require access to your contact list. From the sounds of it the malware doesn't do much other than siphon off your contact list & some identifying information (Android ID & phone number).

Should it be removed from the Android market? Yes. Is it the best example of subversive Android applications? Probably not.