One option springs to mind, but there be a better solution I don't know about.
You don't need to type in the first three letters, one letter should bring up all previously used address with starting with that letter - three just narrows the choices down.
Therefore, if you go through the letters of the alphabet (a bit repetitive I know) you will be able to choose from all addresses you have used (providing you haven't deleted them). If you then select the address you want and click on it so it's underlined in the "To:" box you can right-click and "add to contacts"
Alternatively if you have the email you sent, open it and right clicking on the recipients address will give you the same option.