Bueno por lo que leo creo que el problema fue que la misma empresa que te dio el Hosting te registró tu dominio, ya que de otra forma pues basta contratar con otra empresa y mover los DNS del dominio a los Name Servers de la nueva empresa.
http://www.forosdelweb.com/showthrea...hreadid=132232
Poro otro lado, debes tener una factura o un recibo por parte de la empresa que contrataste, si en esa factura aparece el nombre de tu dominio entonces tu eres el ligitimo porpietario del dominio, con esa factura recurre ante las autoridades, no se si en tu país exista alguna instancia para proteger los derechos de los consumidores, si la hay recurre a ellos, pero recuerda debes tener siempre la factura con el nombre del dominio que contrataste especificado en ella.
Te recomiendo que leas este post:
http://www.forosdelweb.com/showthrea...hreadid=132232
Saludos