When you share an external IP address you not only share the address but you share the viruses too. We get calls asking for help because someone cannot browse the Internet because their service provider has shut down their access due to a virus on their network, or their mail server is no longer able to deliver mail to all recipients because it has been black listed for sending spam.
Because of the advent of Network Address Translation (NAT), which allows multiple computers to share a single IP address, it is quite probable that a mail server is being blocked because of an infection on a standalone PC if they both share the same public IP address. (Note, that this is why if a router supports it, it is always better to have an IP address dedicated to a mail server and the user population using a different address, though on smaller networks, this is not always practical.) Assuming that user PC's are sharing the same address, it can be a daunting task to figure out quickly which machine is infected and causing the problem.
One of my favorite methods for quickly diagnosing which PC is causing the problem is to monitor outbound SMTP (tcp port 25) traffic. Ideally, an internal mail server is the only machine on the network that should be sending outbound port 25 traffic. If personal email is allowed on the network, individual send and receive to external mail servers can occur, but this will be relatively minor compared to the amount of traffic generated by a machine infected by a spam bot. Depending on the network, this functionality can be blocked and logged either temporarily while the problem is fixed, or permanently in a more proactive fashion.
If the firewall supports it, the easiest way to block outbound SMTP traffic is to set up an egress (outbound) rule on the firewall that blocks all outbound SMTP traffic except for that coming from the internal mail server. If the traffic cannot be blocked because of policy reasons, and the firewall can log it (such as with an Untangle firewall that can be either blocked or just logged), the firewall can be an effective way of monitoring outbound SMTP traffic.
If the firewall cannot block outbound traffic (almost all can in some way or another and refer to your firewall documentation) another way of effectively monitoring traffic leaving a network is to install Wireshark (a free network monitoring tool) on a laptop and plug that into an Ethernet hub (or a switch with span port enabled so that ALL traffic is visible to the laptop) along with the external firewall or router and have Wireshark monitor all outgoing traffic. It is possible to limit the traffic that Wireshark views by filtering for traffic destined to TCP port 25. This can be a very effective way of watching outbound traffic for abuse and traffic on non-standard ports. I recently found two bots on a network by looking at high http traffic coming from two machines during a time when our ISP was blocking all outbound web browsing because of a virus infection.
Once the offending PC has been identified, it can be cleaned with various virus removal tools that are available on the Internet. Steps can then be taken with either the service provider or the black listing service to get the block lifted and return things to business as usual. Leaving these blocks in place can be a very effective way of preventing spam bots from doing their damage in the first place and simplify the identification of an infection if logging is enabled.