Do we have to pay to reissue our SSL certificates? If we do then this is the best thing that happened to the SSL certificate vendors and they have all the incentive to be vulnerable
No, you should not have to pay to get an SSL certificate <i>rekeyed</i>. Some providers may ask for money if you want to <i>revoke</i> the cert, if -- for example -- you believe your private keys may have been compromised and you want people's browsers to go nuts if they see that cert in the future, at (for example) a site attempting to MITM you.
This depends on which CA you're using. Some do not have a way to reissue/rekey at arbitrary times (StartCom, in particular), and charge for revocation. Most allow free reissue, and often don't charge for revocation and replacement issue.