From the COBOL Language Reference
Before executing a serial search, you must set the value of the first (or only) index associated with identifier-1 (the search index) to indicate the starting occurrence for the search.
If WS-INDEX-AIX is not the index associated with the table, or you did not use a SET WS-INDEX-AIX TO 1 in your code before the SEARCH statement, your SEARCH could easily fail.
Changing the order of the WHEN clause won't make any difference. Such a change is what I call "religious programming" -- you have faith that changing something
will cause you to get the results you want without any underlying basis for that belief. Before you change anything you need to understand why you are not getting the expected results, which will tell you what to change based on logic.