You did not mention the version of Exchange or Outlook you are using. I’m surprised that only one user is reporting this problem. What is your user population?
It is very difficult to block spam like this without some intelligent filtering in either an edge device or a hosted service. For a hosted service I highly recommend Google Postini. I have around 2000 users in my environment and we are very happy with Postini’s effectiveness. And the fact that it happens “in the cloud” can help your network edge by reducing the amount of bad traffic that has to be processed by your connection and servers. There are other intelligent devices such as Barracuda or Fortinet. See this article on anti-spam appliances for links.
In the IT trenches? So am I – read my IT-Trenches blog.