[auroinfo]

If you paid by a credit card or paypal then issue a charge back immedietly escalating the issue.

As a general rule you are not supposed to pay for a domain name which the provider failed to give at the time or registration.