Thanks for the contributing comments.
I discovered that although we get all incoming mail via a 3rd party spam filter server, we were accepting messages from anyone on the internet. I edited tcp.smtp in the /home/vpop/etc dir to disallow any connections not from our service provider.
Mail was still not going out, but the logs were MUCH easier to read now. They recorded DNS errors, so I looked a little deeper and found the DNS this machine was looking at was not ours, but somewhere else on the Internet, and has apparently been taken offline. I changed it to look to our internal DNS server and all is well.