Microsoft has extended their Innovate on Windows Vista program.  It's a program available to partner ISVs that allows you to submit your application for certification for free.  Note though, that you do have to pay for a secure key from VeriSign. 

(Note that I had bad success trying to get this key.  In my own opinion they are a horrible company because of their lack of service.  In an effort to get the key, they refused to accept validation of my company information.  Their tech support went back on their specifications for proof.)

http://microsoft.mrmpslc.com/InnovateOnWindowsVista/