True, but the IMEI only identifies the phone (the handset), not the user itself. The user is identified by the IMSI (International Mobile Subscriber Identity), which, after the initial login to the network, is replaced by the temporary valid TMSI. The IMSI itself is stored in the SIM card, along with the symmetric encryption key. In order to participate on any network, you need to provide both valid IMEI and IMSI.
The GSM operators should maintain records of the IMEIs used in the network. There are also so called black lists, where banned IMEIs are stored. In theory, if your phone is stolen and you report it, the operator can ban it from being used on the network (and the black lists are supposedly exchanged between operators). However, in my experience, most operators don't care - probably due to the mentioned before easy IMEI change on most handsets.