Leadback.com would be a good place to start...Run by AOL which means broad reach (holds inventory that reaches 95% of US unique's). It is pay per click so it abstracts away some banner CTR risk. They also offer credit terms for new accounts.
Regarding bids for ad networks operating on exchanges (rightmedia, doubleclick, openx, adbrite, adsdaq etc.) any retargeting CPM should be dynamic...meaning the cost of each singular impression changes based on competition for that impression. A higher bid (i.e. $4 avg. cpm) will ensure you get most of the available impressions in most cases, and I believe you received that $4 quote with that point in mind. That said you can still pick up CPM's for under a buck...especially on rightmedia...but volume isnt guaranteed...
All networks operating on exchanges should give you the final authority for cpm bids, with the understanding that impression volume is a function of how cheap you are....hope that helps.