I have a feeling the changes introduced in the Search People feature (in the Home ribbon, formerly Find a Contact) is going to result in a lot of questions down the road, as more people upgrade to Outlook 2013.
I upgraded to Office 365 Home Premium. If I search for a Contact in Outlook, using the search box at the top of my Contacts list, all I receive is the message: "We couldn't find what you were looking for". If I search using the "Search People" box on the top left of the Home page, the search finds the contact. I repaired Office to no avail.
First off, repair won't usually fix things like this. Fortunately, in most cases, nothing is lost but the time you spent doing it. (Uninstall / reinstall fixes even less.)
Now back to the problem. Does a contact exist for this person? Or was it someone you replied to?
Search People includes addresses on the auto-complete list; it is not limited just to Contacts.
If not for approving messages sent to a moderated mailing list I own, I don't think I would have realized this, but with Suggested Contacts removed from 2013, I can easily identify addresses that are in the auto-complete list.
Remove non-existent contacts from Search People
If you want to remove the names from this list, you need to remove them from the auto-complete list, but you can't do it from the Search People list.
You can delete one address at a time by starting a new message and typing the first letters of the address, then selecting the address and deleting it, either with the Delete key or by clicking the x beside the address. Close the message form when finished.
You can clear all names from the list in File, Options, Mail. Look for the Send Messages section halfway down and click the Empty Auto-complete List button.
If a contact really does exist…
If the Contact really exists, try rebuilding the search index and make sure all data files are included in the list of files to search.
To do this, use Ctrl+E to open the search ribbon, then expand Search tools and look in Locations to search. Are all data files selected?
Published February 13, 2013. Last updated on October 17, 2015.