I've used OpenStreetMap before. It is my backup plan if nothing better exists.
I'm looking into the google static maps API now. I don't expect to ever get close to the 25,000 requests/day. It has labels, but the labels only allow single character names (which is stupid in my opinion). Plus when you create the map with labels, you don't know the zoom or center point, so calculating the location of the POIs on the map image is impossible. So I guess I'll have to try to figure out the equations google uses to calculate zoom and what not and try to do it without google's label functionality and implement my own.