Same problem for me. Tried 4-5 times and got alert that I tried too often. No spam filters to eat the email. I finally opened a new account. Did you have any luck? There seems to be NO way to contact skype.
you can try to contact customer service, here's how;
I just had this problem too. It's a ridiculous Catch-22 because there are no ways to contact customer service when you don't know your username and password, even if it's to ask for help getting a new password!
I finally did get around it by acting like I forgot my original e-mail address. When you ask for help with that the page will ask for some billing verification information, but assuming you know that, it will allow you to reset your password and "reset" your e-mail address.
Hope this helps someone else with this incredibly frustrating problem!