If you'd have posted the domain name (so we can do a WHOIS lookup on it) it would have been more helpful.
That being said, there are typically 3-4 contacts for a domain. Registrant, Technical, Billing, and Administrator.
As long as you're listed in at least ONE of these three you have a good chance of getting your domain.
The process varies from registrar to registrar but basically you'll need to call until you find someone who is half smart and wants to help you. Being NICE to them goes a loooong way.
Second... at some point you're going to have to fax in your driver's license, a written statement on company letterhead, and sometimes even a copy of your business license.
Third... from there it usually goes up the chain and evenutually someone somewhere makes a decision and turns the domain over to you.
In my experience, the nicer you are, the smoother things go. The more information you have proving the domain is yours, the better things go. Remember, simply PAYING for a domain DOES NOT mean you own it. (crazy I know)
So... be nice, be patient, and keep moving forward.
In the mean time... you should be able to renew that domain so it at least comes back online for you while you go through this process.
I've gone through this process SEVERAL times with clients. If you need more help, contact me off list.
UPDATE:
I figured I'd update this story for future people who stumble across this thread.
In my experience with situations like this I have found that the NUMBER ONE MISTAKE people make is they call up the registrar and they stop just short of demanding their domain back. Some even go as far as to try and tell "the story". Trust me, the folks at GoDaddy (and almost every other registrar) don't really care about your story.
That being said, I called up GoDaddy on Bill's behalf and talked to a guy in "Domain Technical Support". I explained to him that I was a system administrator helping out a friend who had got into trouble with his domain name.
I also explained that I have two problems. 1) I need to renew the domain to get it back online ASAP. and 2) I need to find out more information about how I can prove I (actually Bill's friend) can prove he is the rightful owner of the domain name.
Short and to the point.
I told the tech guy that the DOMAIN REGISTRANT IS THE BUSINESS but the contact email is the webmaster who is now MIA. With my problem presented to him I then asked "What do YOU recommend as a final solution for this? How can we get the domain back?"
Tech guy said:
Send an email to change@secureserver.net explaining the problem. From there on out, all correspondence will be via email as they keep a record of everything. This is for both their protection and yours. (Believe me, there's lots of domain theft out there)
At some point they will request a scanned copy of a government issued ID. Most people scan their driver's license in .JPG format and make sure it is CLEAR.
He will also have to provide a copy of his business license (or something similar) proving that the he is indeed the registrant of the domain.
Tech dude said the process will take a "couple of days" but in my experience it usually takes longer than that. Plan for 5-7 days of back and forth and if it takes less you'll be plesantly surprised. ;-)