Type- Ahead searching always works on the first sorted column. You cannot use "multiple" searches in this kind of search. You can decide to search in the first sorted column, or in the complete view, but not restrict your search to two columns.
In version 9 to search the complete view, you just need to change the search in parameter in the search window. For versions before that there are unfortunately two different search windows.
The search in first sorted column kind of search window can be opened by just starting to type.
The search in the complete view search window can be opened with Ctrl + F (english client).
If you want to really "search" all occurences, then you need to use the third kind of search in Lotus Notes, the so called Fulltext search The fulltext search bar can be opened using the View - Search this view menu item. It only works (completely), if the database has a fulltext index: Ask your admin to create a fulltext for you, if you are not able to do so.
In that search you can use terms to search. e.g.:
[Name1] CONTAINS "xy" and [Department1] CONTAINS "MyDepartment"
With Name1 = Name of item in document containing the Name you search for (not necessarily name of column) and Department1 = Name of item containing values for department.
FIELD Name1 = "xy" is the same as [Name1] = "xy"
You can find everything about how to use search strings in the Help of your Lotus Notes Client.