UK Nokia cellular phones (prob. not just UK or Nokia though) have an IMEI number in flash memory. This number is effectively the phone's serial number. Also stored in the flash are optional provider flags, these prevent (say) an Orange handset being used on another network.
I don't know about theft prevention as such but what I DO know is there are partial flash ROM images on the 'net that will get around the network provider lockouts (i.e. allow a handset to be non-network specific, innocent use?). Additionally, once you look into this further you will find you can re-write the IMEI number with something else which effectively negates any network provider theft prevention.

My take on all this is that the handset manufacturers need to burn the IMEI number into non-eraseable memory - probably not easy in mid/high volume manufacturing though.

Incidentally, Sunday markets are full of guys with laptops "unlocking" handsets for (circa) £15. While this is probably illegal (because AFAIK they don't own the copyright on the partial ROM images they burn) the worst part is they are possibly unlocking YOUR stolen handset.