The "Allitems"vis a special search folder created by Outlook which has the scope of everything in the mailbox which has an item class. While its useful to user there can be some big drawbacks. First it’s an Outlook application folder – ie it’s just meant for Outlook to use. If Outlook isn’t used against a mailbox then it might not exist. If you do a search against a mailbox with lots of items using it then you might get a time out because your trying to eat an elephant in a short amount of time (i.e. the timeout value). Its better that you create your own search folder rather than rely on this folder existing - you can also better define your own search folder for your own uses. Working with the AllItems folder is best suited for things like sync subscriptions and not searches against large mailboxes. However, it’s not a standard folder – it’s an Outlook one. Since it’s not a standard Well Known folder and your application did not create it, you should really should not be using it.
Searching against the AllItems search folder usually works well as long as the mailbox does not have a lot of items. The more items, the longer searches take – that same logic for everything which supports searching. In mailboxes with a lot of items, lots of folders or where intensive searches are being done there is a chance that you will get a timeout error. So, for searching all folders while you could usually get away with searching against "Allitems", there can be some issues. To avoid timeouts its best to get get folder structure and then walk it and do a search against each folder – this may take longer but the chances of getting a timeout should be greatly reduced.
Here is general information on creating and working with Search Folders:
Creating search folders by using the EWS Managed API 2.0
How to: Work with search folders by using EWS in Exchange