What version of Windows? In WinXP, the firewall blocks the program from accepting inbound traffic, it doesn't block it from outbound connections. In Vista, you can use the "advanced mode" of Windows Firewall to regulate both. Alternately, you can install a third-party firewall.
If the program in question only uses a specific set of ports and they're not ports you use for anything else, one option is to block them at your router.