This is not a realistic attmept to to solve the problem, but rather a rough brainstorming, or chucking ideas in and see what happens..
Does a longtitude and latitude pair represent one coordinate on the map?
Could you define up front all possible locations for a clickable circle, then build the imagemap on demand, just making active only the circles that have something in the database/query/current instance (whatever)?
Could you split the whole map into however many maximum peices would ever be needed, then put the bits in a big table with no borders, sort of thing.
Are you talking about actual client-side image-maps? Can you make them dynamically?
Maybe you could do something funky with DHTML if every table data element is a DHTML element between <DIV> tage and named as a coordinate, sort of thing. Or mess about with layers.
Or something. Just throwing ideas around. Hope it helps
Gregg