We have been using BMWinPlus for about 4 years and are very happy with it. It costs about $400 per year for the license($100) plus the post office mandated quarterly update discs($300). This includes the shipping on the update DVDs. The program itself includes free unlimited updates.
Also, you proably need to be using some address update service if you aren't already. We have been using a NCOA that costs us about $30 per batch (up to 10,000).
If the costs seem too high, I would suggest running the numbers again using $0.44 for First Class versus the about $0.16 for bulk mail. If you are doing any significant amount of mailings, the software easily pays for itself in postage savings.