need help handling spam relay.

Several of our contacts claim that a spam was sent out from our firewall (Sonicwall SOHO3). The IP was our firewall’s NAT public address.
We use a third-party mail server. Since this our first incident, how to begin troubleshooting/tracking down this issue?
Please input is greatly appreciated.