Вообще кажется очень сомнительным, чтобы это была связь именно с ОС (типа на семерке одним образом, а на XP - нормально), нужно наверное более точно закономерность выявлять (версия офиса, тип адресов, тип сервера, через которых доставляется и т.п.) .
Начать можно:
1. Почитать вот это
http://support.microsoft.com/kb/831607 и посмотреть на проблемных машинах те параметры, о которых там идет речь.
2. Проверить, что у проблемных юзеров стоит в Свойствах сообщения - Формат для интернета (это по двойному щелчку на адресе в карточке контакта).
