I believe "search" wouldn't find any folder that is not listed. It's just a help of finding something when you have a long list of folders.
I have not used Office365, but I remember Kostya mentioning here earlier that you can not access "shared" folders in Exchange accounts (and I am not sure if that was via EWS only or both, EWS and IMAP).
You are not talking about those, are you?
Besides that, - sorry, I don't have any other ideas at this point.
Maybe Kostya will have some suggestions.
Just in case, are you sure you are using EWS or IMAP type of connection to your account, and not POP3? But then, you said you could create and use some folders, which is an indication that it must be EWS or IMAP.
Maybe you can post a screenshot of the screen when you open "other folders", cann't you? Maybe that would give some clues of what's happening there.
Also, please mention your device's Android version (in case Kostya is aware of some peculiarity with the built-in libraries in some versions).