I don't think the argument here should be is it legal or not to change the IMEI. It should be more, why do you want to?

I think (I have to check) but 3GPP does not require, by legal requirement, a handset manufacturer to provide a unique IMEI for a handset - yes it is very useful, and helps alot, but I don't think it is required to validate the device tecnically.

Some operators don't care about devices without IMEIs - there has been millions of fake Nokia/Blackberry/Sony Ericsson devices used on networks in Pakistan/India/China for years. All these devices have had a) cloned IMEIs, b) no IMEIs.

I would be more worried about the affect it would have on the device's operation on the network.

If you are doing it for illicit purposes (stolen/fraud) then you deserve to get caught. If its for valid reasons, then away you go, but be warned..