Hi,
Using 11.4.6 on Windows 7.
There appears to be a bug with contact folders. Here's how to reproduce it:
Goto contents section of Outlook
Choose File -> New Folder
Choose Contact and make a new folder e.g. "test"
A new contacts folder appears in the list
Add a new contact to it, et.g. testcontact
Now right click on the folder and choose Delete test
The folder dissapears
Enter "testcontact" in the search address books field
The deleted contact testcontact shows up. It even shows that it is from "test" folder in the bottom left corner: "In Folder: test"
Now delete the contact.
If you try to find again it it is still there!
Exit Oulook
Re-open Outlook
Now it is gone, i.e. it does not appear if you search for it!