I call Orange a lot for IMEI checks. If it's blacklisted then it either belongs to someone else or the host network. So we can seize it & call the police, depending on how much of a smack-rat the person trying to sell it is.

IMEI changes can be very easy to do, if you have the right equipment. As far as I'm aware there's no solution for the Iphone, Nokia handsets are bullet proof to IMEI changes as are Sony Ericsson A2 handsets (although a solution does exist but is not being made public). HTC & Blackberry handsets are unknown to me as I don't have access to the hardware, but my instinct tells me they are secure.