First check your spatial indexes. You can create them using a SQL statement such as
CREATE SPATIAL INDEX MyIndexName ON MyTable(GeomFieldName) USING GEOMETRY_GRID
WITH (
BOUNDING_BOX =(-1493907.5664457313, 6128509.51667404, -578861.3521250226, 7703103.135644257),
GRIDS =(LEVEL_1 = MEDIUM,LEVEL_2 = MEDIUM,LEVEL_3 = MEDIUM,LEVEL_4 = MEDIUM),
CELLS_PER_OBJECT = 16, PAD_INDEX = OFF, SORT_IN_TEMPDB = OFF,
DROP_EXISTING = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)
A key parameter to change is the BOUNDING_BOX. This sould be set to the bounding box of your data, or maximum bounding box of expected data. So if your data is restricted to North America, set the bounding box to the extent of North America rather than the world.
You can add calculated fields to show the bound of each feature as noted at http://geographika.co.uk/sql-server-spatial-sql - and can then use a standard query to see the maximum extents.
Also check using profiler to see that the indexes are actually being used. Sometimes you have to force their use with the WITH (INDEX (MyIndexName)) statement.
SELECT *
FROM MyTable
WITH (INDEX (MyIndexName))
WHERE (geometry::Point(@x,@y,3785).STWithin(MyGeomField) = 1)
I have also found that sometimes it is quicker when querying by points not to use a spatial index, so it is worth experimenting.
Alternatives
A final option would be to create a trigger when a new record is added that would assign it a polygon ID when it is created or updated. This would allow almost instant queries on your data.