How many flight plans are you running per month? There are a few providers that have a pay per use in addition to fleet pricing: AirData and PPS come to mind.
Personally, I like Navtech, but I have not used their new program. The demo looks good though, and I would use that program.
Another (relatively) budget flight planning program is SkyPlan, also out of Canada. Still another one is Universal Weather in Texas, they do not offer their services to US Part 121 airlines though, so if you are a JAR equivalent, they might not be able to service you either.