These are the very situations that demonstrate that you should always keep your domain registration and hosting separate.
Brendan, do they have a domain control panel or anything? Often you can open a domain up for transfer and transfer it to your GoDaddy account or something.