Most notably Gmail allowed downgrading to insecure connection until the China affair. There are other mail, messaging and social services people use there, some of them regional (e.g. Russian), where perception of security threats is low.
Cell towers per se do not maintain any logs, it is just transceiver equipment connected to communication line. However telecom datacenters provide location services based on signal strength from the handset to cell towers in the area. Many operators make these services available commercially to customers, and the data is nearly always accessible to law enforcement upon request.
Wikipedia provides a good summary of the process: http://en.wikipedia.org/wiki/Mobile_phone_tracking