Unfortunately, as of today, the web client still insists on sorting by relevance regardless of the setting you have chosen for your notebooks.
For the life of me, in any product, not just Evernote, I have never seen any value in "By Relevance" as a sort order for search results. I don't know what definition of "Relevance" is being used, but it has never resulted in anything but a random mish-mash of results slapped together with none of them being terribly relevant to my search need.
"By Updated" is the only way I've ever found the results to show up in any useful /useable manner. It will be great when Evernote fixes this omission.
Best Regards