I have a large contingent of Macintosh users, some using Mail, some using Entourage, all with the same problem that has come up suddenly. They can't send any email with an attachment through our exchange server. I've done everything to diagnose or solve this problem EXCEPT reboot the Exchange server, which I am saving for an absolute last resort. I've been searching for an answer to this, and have yet to find one.
An addendum to this; these same affected users cannot use the web mail service to attach a file to an email.