I've heard that IMEI numbers are stored on an EEPROM, essentially letting them be erased and rewritten. Thieves misuse it to make stolen phones untraceable. Is there a reason why manufacturers don't use one-time programmable non-volatile memory for this?
Manufacturing costs are the primary driver of this flexibility. While phones often have many names on the outside, on the inside, there are a much smaller number of actual hardware manufacturers. Since one hardware builder has to create kit for several OEMs, it is much easier to build the systems with EEPROMs that can be reflashed again and again, so that product which fails a test while being built for Manufacturer A, can be reworked, reflashed, and end up shipping for Manufacturer B.
In the olden days, when on-board ethernet was a new thing, MAC addresses were originally distributed as you suggest, on non-modifiable chips. This meant that when a partially completed board made it up to test, and it was determined to be faulty, the company building on-board ethernet devices for manufacturers A and B had to keep a log book of all the thrown-away MAC addresses, so that more chips could be burnt, so those addresses wouldn't be 'wasted'. Once they moved to putting MAC's in EEPROMs, failures could be reworked, while the MAC addresses were returned to the pool of available numbers instantly.
In some countries (I think China is one), regulations require the phone's IMEI to change each time it's repaired.