They're stored in a file with an NK2 extension.
Methods for migrating your NK2 file are described here:
http://www.ingressor.com/autocompletetips.htm

Signature
Russ Valentine
[MVP-Outlook]
> Hello all
>
[quoted text clipped - 12 lines]
> Outlook 2003
> ===
henpat - 08 Mar 2006 11:07 GMT
Thanks a lot
henpat
------------------------
> They're stored in a file with an NK2 extension.
> Methods for migrating your NK2 file are described here:
[quoted text clipped - 16 lines]
>> Outlook 2003
>> ===
> I have my "normal" forder to manage my contacts.
> But I have also a lot of mails that appears automatically when I
> write the first words... I need to recover all these e-mail that are
> in the memory/registry...
In addition to the commercial tool Russ mentions, if all your recipients are
Internet recipients, then the freeware tool http://www.epute.com/nk2csv/ may
be sufficient.

Signature
Brian Tillman
henpat - 08 Mar 2006 14:16 GMT
Thanks... very useful
henpat
>> I have my "normal" forder to manage my contacts.
>> But I have also a lot of mails that appears automatically when I
[quoted text clipped - 4 lines]
> are Internet recipients, then the freeware tool
> http://www.epute.com/nk2csv/ may be sufficient.
Russ Valentine [MVP-Outlook] - 08 Mar 2006 21:17 GMT
Ummm... I wasn't recommending any commercial tool.
That site just tells users how to migrate their NK2 file on their own. It
doesn't require any tool.

Signature
Russ Valentine
[MVP-Outlook]
>
>> I have my "normal" forder to manage my contacts.
[quoted text clipped - 5 lines]
> are Internet recipients, then the freeware tool
> http://www.epute.com/nk2csv/ may be sufficient.
Brian Tillman - 09 Mar 2006 14:04 GMT
> Ummm... I wasn't recommending any commercial tool.
The site containing the page you cited does, and that's what I meant. I
should have been more precise. Since the OP said "recover" the data and not
"migrate", I read the intentions differently than you.

Signature
Brian Tillman