Thanks again. Here's what I did that helped.

First, most of the problems ended up being city names like Flint Twp instead of just Flint. Normalizing with Geo::StreetAddress::US and removing city suffixes like Twp and Vlg got me down from 50 to about 15 failed addresses. A few more were fixed by changing mt to mount in city names, and that got me down to 10. 5 of those worked with other, more costly services.

What I'll probably do is write a Geo::Coder::BargainHunter module to try http://geocoder.us first, then http://geocode.com or similar for the trickier addresses.

The filter_ranges method looks useful, but it can't be called remotely over SOAP, and I don't have a local copy of the database (though I may go ahead and get one if we go live with this).