Unfortunatly what happens with Y! tech support is that it's out-sourced, so the support reps are given specific instructions on what is and is not viable verification info. And usually the questions asked will depend on the department you reach.

The basic questions are: Zip code, Alternate email addresses, last 4 or 8 digits of credit card number, Billing address, birthdate, secret question and answer.

Everything but the birthdate and Secret question and answer can be accessed and changed if you can log into the account (Billing info obviously requires access to the Y! wallet, and hence, the security key), otherwise it's information you should know. Remember, its part of the terms of service to provide truthful and accurate information (Or, you should, atleast write down the info that you do give so you aren't left guessing when problems occure.)

I do think however that there should be some alternate form of verifcation available. Like a "Registry confirmation code" that you're given, once, randomly generated and stored in the Y! user database that can be accessed if everything else is forgotten.