I have not used them yet but I've had several people recommend http://www.elegantbanners.com/. Their sample work seems nice and banners start at $20, so it may be worth a gamble.
Find out if their clients will go on the record for improvements in conversion rate or how well they work for them. With banners, as always, your goal is to make money. Gauge their work based on that if possible.