CheckPoint's ZoneAlarm firewall has been updated for Vista compatibility, quite a ways post the Vista release. Version 7.1 of the firewall suite, one of the more popular software offerings, brings this added support. This makes it the first incoming and outgoing software firewall that is fully compatible with Vista. The reason for the delay in bringing compatibility, says CheckPoint, was quality assurance and future-proofing for development of the suite as Vista matures:

Rather than rush to market with a patchwork solution when only a small fraction of our users were actually using Vista," the company said, "we decided to invest in the long-term." This includes building the product on Microsoft's Windows Filtering Platform API, rather than continuing to use the soon-to-be outdated TDI API. Not only does this provide ZoneAlarm with more stability under Windows Vista, but it means Checkpoint won't have to rewrite its code when TDI does expire.
Both the paid version and the free version of the software have been updated. If you're looking for something stronger than Vista's built-in firewall and don't have a hardware solution, this is definitely one to check out. You can download the software from the Zonealarm site, though as of this article they were presenting the 7.0 suite rather than the update.