A mobile wireless communications device is to communicate with a server storing a plurality of file folders, and includes a display, a wireless transceiver, and a processor all carried by a housing. The processor is configured to wirelessly download an initial portion of a selected file folder from the server, with the server still having a remainder portion of the selected file folder available for downloading. The processor also generates search results by performing a local search of the initial portion of the file folder, and performs a remote search of the reminder portion of the selected file folder. The processor further presents the search results on the display.