Just block it in Windows Firewall. You may have to click on the "Add a Program" button to get the program onto the list of exceptions (and then make sure that it isn't checked).
I'd be interested to know what the program is if it's bypassing Windows Firewall. Actually, I'd be inclined to remove such a program from my PC - if it's bypassing Windows Firewall goodness knows what else it's doing.
I think you must be right. The firewall on Windows 7 claims to be able to block outgoing programs, but I can't get it to work. Never mind, there are plenty of other firewalls; I'm sure that one of them will do the job.
Personally I'd get rid of any program that doesn't allow you to turn off automatic update checking.