openmoku ?

The only reason it is illegal to change the IMEI in the UK is because that's
what is used to track people.  Mobile companies collect and store data for
years - so they can tell which phone uses which numbers and who is using
stolen phones if reported.  Changing a SIM doesn't hide a stolen phone and
numbers in and out of the phone are cross referenced.  The same goes for
text messages.
Mobile companies provide data to companies such as Technocel who put it all
together in a report for use in legal proceedings.  Data on location is also
stored and with more cells it can trace people to within a few feet.  Its
very interesting to see the reports.
Mobile companies could do something about stolen phones but choose not to,
they could also stop insurance fraud - people using it as a cheaper way to
upgrade etc.  Access to the data is not authorised for phone sales people or
repair departments by the way, so people on a help centre line will not know
about what is stored.

Changing software and debranding is not against any Law I can think of,
although it might be against the contractual agreement with a mobile
company.  There is no way they would know unless you waved it in their face.
Debranding can take away annoying features you don't want, or change the
function of buttons or menus.  Rather than being directed to premium
services you could use a chosen one.  Updating firmware is an advantage to
keep up to date.