Simon, Gunter, thanks for your input. I also noticed that an index on (gx,gy) would help on covering index searches, however as you both noticed as well there are more fields in this table. But wait - probably for the first step (which points are located in the region in question anyway?) it might well be enough to know the coordinates and the object ID, the second step (user needs to know more about a certain point in this subset of points) could probably a separate query in many situations. I'll have to investigate this in more depth.
Thanks again! Wolfgang