Telcos can track imei's. There is no doubt on this. Part of the normal information that a handset sends to the network regularly is its imei. Obviously each network can only track an imei that is on it's own network. For a telco to give the police (or anyone else) the details of the user whose sim is in the handset, they would require a warrant. Most police will not even bother.
Most carriers in Oz now block stolen imei's and have cooperation agreements in place, so that the imei's can be blocked across all participating networks. However, this isn't to say that correct normal procedures are in place at the "front lines" to make use of this facility.
Generally, telco's don't care if your phone is stolen. In fact, they prefer it if you can't get it back because you are likely locked into a contract of sorts. If not a service contract then a contract to at least pay for the handset (that was stolen). Most people will just fork out the dough for a new handset (more $$$ for the telco).