My search in Outlook 2007 doesn't even find a keyword or contact that I can
see in the inbox.

Could this be something to do with opening a new personal folder (brought in
from another PC). How do I set it to search the correct Personal Folders?