Sure you're not confusing IMEI blacklisting with simply unlocking your phone? Because it sounds like what you're describing is a locked phone and that you're roaming, i.e. it will only work with one carrier's SIM, and you can't use a SIM from another carrier in different a country with it. If it's just unlocking, that's only illegal in America AFAIK. Many independent phone dealers should be able to unlock it for you, the sort of places that's often found in shopping mall stalls and kiosks. In fact your carrier might be able to unlock it, if you tell them you're travelling overseas. Probably the reason you're paying a lot of money is due to the fact it's doing international roaming. If you get the phone unlocked it should work with a local SIM no problem.
Changing the IMEI is illegal in many jurisdictions and countries. Usually IMEI blacklisting only happens when a phone is reported stolen or missing, or for defaulting on a contract(in the US). If a phone is IMEI blacklisted in one European country, e.g. Turkey, it won't work in any other European countries. Because AFAIK IMEI blacklisting covers all European carriers, with a Europe wide database of blacklisted IMEIs.