First of all, did they tell you what virus they think you have? If so, go to one of the anti-virus vendors' websites (e.g.
www.sarc.com) and search for that particular virus - it should tell you many details about how you can tell if you're infected, and so on. I presume the internal boxes are Windows boxes?
Secondly, many viruses fake the senders' address: so just because the ISP thinks you're infected doesn't mean you are. Again, the description of the particular virus on the a-v vendor's website should tell you whether or not it behaves like this.
Alternatively, log in as root and run 'tethereal' (you may need to install it first). That shows you what packets are going through your network interfaces - it's probably easier to do this here than at the firewall. If you know what you're looking for (you say the ISP sent you sample logs?), then pipe the output through grep and you'll see what's happening soon enough.
For example:
root> tethereal -i eth0 | grep 69.50.188.180
...(where eth0 is your outside interface) should show up traffic to the ip address 69.50.188.180, which is a potential symptom of Trojan.Flush.C, which Symantec currently report as one of the top five virus threats.
However if you do want to log outgoing traffic at the firewall, then that depends on which firewall you use. I use iptables, and I would do something like this:
iptables -A INPUT -i $internal_interface -m state --state NEW -j LOG --log-prefix "IPT_NEW_INT: "
iptables -A INPUT -i $internal_interface -m state --state NEW -j ACCEPT
The first line logs the traffic, the second line allows it through.
then just keep an eye on the logs:
root> tail -f /var/log/messages | grep IPT_NEW_INT
...should show up any new outbound connections being initiated. This is my least recommended method of checking, as it's the least likely to succeed.
If you tell us which virus they think you have, someone can tell you in a bit more detail what sort of thing to look for.
Hope this helps
Weegolo