Since there is no easy way to search in all folders, I was relying on fetching the emails from "All mail folder"
store.getFolder("[Gmail]/All Mail")
However, this breaks in international editions like Italian where All Mail is localized.
How do I get the "All Mail" folder for all international implementations?
Use Store.getFolder("[Gmail]").list(). On the returned Folders, cast them to IMAPFolder and use the getAttributes method. One of them should have a "\All" attribute. See the folderlist.java sample program for example code.