Propably the Unique Code you received through e-mail when you made a Lineage II account, the date of birth and your first and last name. And accounts name of course :)
I was really mad at first that I was unable to get help. I called and called and got through finally today. The staff was actually really nice and once I was able to give them the info they wanted they reset my pass and I was ready to go. So for all those still waiting yeah it sucks but they are still working. I'm not real sure about the response time on emails (I got an email update on my call from the rep I spoke with after we hung up), so maybe the call staff and email staff are the same. If you have enough info to show them that it is your account they can help.
I got them on the phone, they wanted some of the following:
CD Key
Original credit card used to pay for the account (I started this account with a game card and they let me supply them with the first credit card I payed with.
I can also say the first person I got didnt help me much, and I was pretty irrate with her. I was nice to the second guy though and he helped me. So make sure to be friendly with them, hey it can't hurt.