If you have large numbers of point to look up and/or large numbers of polygons to match against, then you may find Re: Speeding up ... (O(N) determination of point in polygon regardless of complexity) of interest. It demonstrates a method of O(1) lookup (per point) regardless of how many polygons you are matching against. Well, up to 4 billion polygons.

That is, to lookup any 2D point and determine which of upto 2**32 polyons it is in, takes one memory read.

In that case it was finding the zipcode for a grid reference anywhere in the US. Which doesn't sound too dissimilar to the sketchy details you've given. It's quite simple to program and very fast.