Have you seen the Medieval Herb, Plant and Flower Illustrations and 200 Illustrations from Gerard's Herbal clip-art sets? Dunno if they'd be helpful to this particular project -- I have the Gerard set as part of a larger software package, and have used it for some Elizabethan-style embroidery -- but they could be a good source of illustrations without copyright worries for future projects.

I have a couple of those new Dover CD sets and I like 'em a lot. The fancy graphics on my website are based on another set in that series. :)