Not just Go-Daddy
I had pretty much the same experience with another Hosting company recently.
Company website setup and registered by an employee who had now left. I had to get into the hosting control panel to be able to update the whois details and billing info.
i called the tech support people, gave them the whole story, they said unfortunately they couldn't give me access without some form of lengthy verification involving photo ID, letter headed paper, faxes etc....this was all too long....
SO, i called them the next day, and pretended to be the original domain register (the ex-employee who left) i said i was having some issues getting into the account, they said they'd send me a confirmation email to get access back to the account -i said that wont work as we are having email issues at the moment, they said OK we'll call you on the number registered to the account (the main reception number) i agreed to this, i then called reception, told her of the imminent call and when the person asks for "[ex employee's name]" to put them through to me......sure enough 5 minutes later they called reception, got put through to me to which i answered "hello [ex-employee's name]" - the guy was happy he had got through to the right person and i was then granted full access to the account and was able to change everything.
*legal disclaimer, it was our site, we pay for it and manage it, no laws were broken in the making of this post.