Hello,
The First thing to do is identify the Registrar for your domain. If .com, .net, .org, .bix or .info then look here:
http://www.internic.com/whois.html
If it is another TLD (Top level Domain) then you would need to locate a whois for that TLD, possibly Register.com as they cover a wide range of domains.
http://www.Register.com/
Once identified then look up the full whois information for the domain, at the actual Registrar of record, and see who is listed as the Owner/Administrator and if the contact information does not match yours then find the best method to contact the Registrar, phone if possible, and explain the situation to them.
If you find that some or all of the Owner/Administrative contact matches you or your companies then you would have less problems...
I would advise you not to setup new hosting until you have secured the Domain Name and only consider ordering any hosting services after you have full control over the domain in the event it becomes a dragged out affair or you cannot secure it at all
Good luck,
Bob