Geo-coding and spatial calculation products

Hi, our company is currently using Envinsa from MapInfo to meet our
geo-coding and spatial querying needs. We are trying to find some
cost-competitive alternatives--would very much appreciate any
recommendations. Who should we be looking at? Here are our basic
requirements:

On the fly geo-coding:
- several million requests per month
- response times are about 20ms using our current solution
- for the above reasons, a server based solution is desireable (as
opposed to using a web service)
- we require good precision--TIGER base files are not sufficient.
We require the quality of a NavTeq or TeleAtlas underlying data set
- assuming server side, we would look for data updates 3 - 6 times
per year
Windows or linux are acceptable platforms
For the spatial querying, the key integration points are:
- the data for the queries comes from two sources: information
stored in MySQL and the incoming address for the on the fly
geocoding. Similarly, a single polygon could come in via that web
service.
- we do NOT want a system that uses MBR (minimum bounding
rectangles) to determine point in polygon.

Many thanks for your suggestions!