I was able to get my pay-as-you-go phone unlocked by my network provider (Orange) free of charge when I moved back to the UK. In France, your original network provider is legally obliged to provide you with the unlock code for the EMEI number provided you've owned it for more than 6 months. If you request it prior to the 6-month deadline expiring, then they can charge you .....Orange quoted me €20.
I'd check whether such a provision exists with your original provider, before trying it elsewhere.
Nokia phones, on the other hand, are easily unlocked using freely available tools on the web
