[aESThete]

hasherfrog

У меня пользователи (вроде все уже наученные горьким опытом) клянутся и божатся, что они не открывают "никаких-таких вложений". Но вируса как-то просачиваются. Значит, всё-таки открывают?

ИМХО не обязательно, вирус может быть в html-коде письма. Да и может все-таки открывают.

...и примеры действенных мер из жизни...

Издать служебное положение (или приказ) "Об использовании электронной почты и интернета". Все протоколировать (логировать). На провинившихся составлять официальные кляузы с указанием конкретных фактов (из логов, протоколов антивирусников). Бить по карману.

И заставить "тамошних" не могу.

Хм... Вышестоящая организация? А если не заставить, а попросить. И еще хотя бы присылать логи.

Был вроде простой вариант - поставить антивирус для почты на каждую машину. Но тут же пошли жалобы, "медленно работает".

Н етолько простой, но и правильный. Вам (нет, даже не так - фирме/предприятию/руководству) скорость важна, или безопасность? Да и не так уж и сильно замедляется.
Поставьте какой-нибудь "нетормозящий" антивирус. (от Symantek как советует noble, или DrWeb)