I don't know if it is of any help for you, but in Austria unlocking is legal.
Semaf Electronics - www.entsperren.org / Startseite, they unlock everything: cellphones, sticks, datacards, Iphones etc. for little money (around 10-20€)
For instance, I bought in Germany from Conrad Electronic a Vodafone locked VF125 for 5€ (with SIM, new), took it to semaf in Vienna an had it unlocked for 10€.
This phone and other cheapies were also available from Quelle stores and other electronic retailers.
It's a simple mobile, but works smoothly.
For Nokia phones, you'll find austrian (google.at???) websites providing the unlocking or safety master code for free.