I have had lots of trouble with various so called hosting servoces in the past.
The key here is who is listed as the registrant when you do a whois. If it is you, I don't think you will have a problem getting the domain name back in your control. You might have to jump through some hoops to get it done. You have to contact your registrar by phone or whatever to get the proccess going. You need to change the administrator of the domain to yourself.
If the registrant is not you, then you may have more serious problems. If this is the case, the company you hired did not register the domain name on your behalf, they just registered it to themselves and now claim ownership. I have seen this in the past and it is a sham that some companies will try to pull on you. I think the only recourse if this is the case, would be the courts. I would keep all docs, related to this in case it comes to that.