First, since you stated you had to re-install your Outlook 2003 client, this suggest that the auto name resolver cache file or NK2 file was most likely removed then re-installed. This would have removed any auto resolving email address. Compose a message and sen it to any contact. Once sent send a second and see if the TO field auto resolves.

For your second issue, this is not normal behavior for the search functions of Outlook. check when searching you are doing it in all Outlook contact folders. If not try this link:

http://support.microsoft.com/kb/831402

http://www.eggheadcafe.com/software/...look-2003.aspx

Hope this information was found helpful.