The Query Builder allows you to control the AND and OR relation in your searches

Note: 12.0 in the path below is the Outlook version, replace it with the Outlook version you have.

Credit for this trick goes to: http://www.msoutlook.info/question/276