Your first recommendation includes this statement:
"...just make sure you set up OWA so that the Linux users can access Web mail."

AFAIK, OWA does not support email message encryption. So, now, with 1/4 of the desktops required to use OWA, it seems to me that you've just *lowered* security vastly.