IMEI = International Mobile Equipment Identity number

It identifies the actual phone. It doesn't not identify the phone
service in the GSM system. That is done by the IMSI (International
Mobile Subscriber Identity) which is stored in the SIM (Subscriber
Identity Module??).

A locked phone is one which will only accept a SIM for a specific
network provider. Unlocking allows a SIM from any network be used with
the phone.

Just because the number is unique does not mean that it can't be
changed. A phone number is unique and can be changed. On a lot of phones
the IMEI is stored in a memory location which allows it to be changed by
some means. It had to get there in the first place. For a lot of
networks and countries, when a GSM phone is stolen the IMEI is added to
a database of stolen phones. The phone is either blocked or tracked.

Not all networks record the IMEI of stolen phones. Some only store the
IMEI of phones stolen on their network. Sometimes networks in the one
country share the list. It is also possible to share among multiple
countries.

As an example, the networks here in Australia only recently kept a list
of stolen phones on their network. That was the first step. Now the
networks share the details, so a phone can't be used on another network.

Managing the list is not as simple as having the list exist. It is also
quite expensive. From the networks point of view, they don't really care
if a phone is stolen. A phone that is blocked is one that can't be used
to provide them with revenue.

Of course, if you wanted to use a stolen phone on a network which blocks
stolen phones you need to change the IMEI. Are there any other reasons
to change the IMEI? I can't think of any. So if someone wants to change
the IMEI of a phone, it's probably a stolen phone.