It will take my company literally months to push through a contract for something like this. Google will be required to tender, alongside other comparable services. I just don't see that happening...
It's possible to get 50% discounts of the $4 price (if you do more that 100,000,000 per year)
Any contract we sign needs to be for a fixed price, rather than a variable amount. And amounts above a certain limit need to go out to competitive tender, which takes a long time. (I'm not sure Google or the other players in this space would even bother to tender anyway.)
So the only option remaining is to rebuild the mapping solution using another technology to ensure continuity of service.
Presuming you don't, perhaps you could find a way to get your superiors to think of things like map requests as akin to coffee or paperclips rather than a service or a piece of boxed software.
Do you have any insight into how large the volume of your map requests is?
http://www.google.com/enterprise/earthmaps/maps.html