An email system may include an email server(s) configured to store email messages in a plurality of mailboxes, where the email messages are organized into different conversations and the conversations are organized into different categories. A plurality of mobile wireless communications devices may each be configured to store email messages from respective mailboxes also organized into the different conversations and the different categories. Each of the mobile wireless communications devices may also associate respective conversation IDs with the different conversations, and associate respective category IDs with the different categories. An email synchronization server(s) may be configured to synchronize email messages between the mobile wireless communications devices and respective mailboxes, translate an email search request in the form of a conversation ID(s) and a category ID(s) from a given mobile wireless communications device, and cooperate with email server(s) to retrieve email messages based upon the translated email search request.