Sure, for sending/receiving the email all of that is accessible/needed but some (all, even) of this could be stored encrypted by the user's password/mailbox-pas

Sure, for sending/receiving the email all of that is accessible/needed but some (all, even) of this could be stored encrypted by the user's password/mailbox-password. If I remember correctly: one of the reasons they don't encrypt that metadata is so they can do the search box server-side.