According to Google Support you can use the recovery link on this page: Recovering sign-in information
From here, you should try with all accounts you are associated with to see what accounts are linked. (Assuming you remember all email accounts used apart from the one you forgot). It is sort of hit and miss but it has worked for me on two separate occasions.
You should get an email similar to the following.
Your recovery address, phwd@gmail.com, is associated with:
xxxx@gmail.com
xxxx@gmail.com
xxxx@gmail.com
xxxx@gmail.com
xxxx@gmail.com
To sign in, visit the link below.
http://www.google.com/accounts/
If you've received this mail in error, it's likely that another user
entered your email address by mistake while trying to recall their
username. If you didn't initiate the request, you don't need to take
any further action and can safely disregard this email.
If clicking the link above does not work, copy and paste the URL in a
new browser window instead.
Thank you for using Google.
For questions or concerns regarding your account, please visit the
Google Accounts FAQ at http://www.google.com/support/accounts/.
This is a post-only mailing. Replies to this message are not
monitored or answered.
As seen above it works for multiple accounts. So any account that has phwd@gmail.com listed is brought up in the list.
Additionally you can search your email accounts for the following subject line
Your Gmail address has been created
This will bring up (if you didn't delete it), the confirmation email messages of all Gmail accounts you used the current account as a recovery point. Although, based on "used in ages" I am not sure how far back Google used to send out this message.
Google is probably using information that it has not specifically requested of you during the password reset process in order to verify your ownership of the account. Specifically, tokens stored on your computer, and your IP address.
I had a similar experience to yours, which initially alarmed me, and tested the above theory by using the Tor browser to perform the reset. This browser redirects a Web session through Tor's own servers in Europe, making your session more anonymous.
The result was a much more aggressive set of questions. The first time I attempted to reset the password, I just blew them off, and hit a brick wall. I tried a second time, and once I had answered the questions somewhat correctly, I was presented with an emailed link to a reset page. When I clicked that link, since I have two-step verification set up, I was presented with a demand for a number provided by the Google Authenticator app on my phone. I provided that number and only then was I allowed to reset the password.
This experience gives me more confidence in the process. Google, while fallible, is not a huge corporate playpen full of idiots. Password security is a critical feature of Google's business, and I'm sure that they have thought long and hard about how best to allow legitimate users who are schleppy enough to lose passwords to get them back without allowing thieves to run off with all the Google accounts.
Best Answer
If you know the User-name and password, then you can just log in without having to do any password recovery.
And once you have logged in, you can go into the settings and see what primary email address is associated with the account. And you can change it - provided it's not a gmail address (but it it is a gmail address, then your user-name will be the same as the email address).