I did this, and have since regretted it. Ever since I registered my domain name with my ex-host I had one fundamental problem. My host kept the name servers pointed to their servers only. Forcing me to stay with them as my host.

This probably isn't as bad as the story gets, being frustrated I started to investigate the domain issue and found sedo.com who claim they have an 80% success rate in acquiring domains for you. Yes they are very expensive to use, but they got the job done like a charm!

The big issue is that sedo were able to obtain this domain from my host, without my host actually knowing who the domain was going to. I was not contacted from my host to say they were selling a domain I had originally 'bought' from them. I don't know much about the legalities here, but I can guess what they did was probably not legal.

Who were you hosting with? Did you read through their Terms of Service. If you DomainWHOIS your domain and it is registered to you, then you are fully entitled to aim it at your own servers. If it was registered to them, read their TOS and take them up about what they are doing. I agree with you that it is grossly unfair what they are doing to you!
~Equinox

Our policie is that we recomend to clients, if they want to leave our company, to transfer doman with diferent registrar. If thay still want to have domain with us, we will change name servers upon request.

Yes, it has been the same with most of the reseller accounts I have used.

most reseller are enom's and there is a domain management for you to point your own name server. Try looking for some alike.