OK so the query looks as follows:

SELECT

<fact table attributes>

,Tr.Country

,tr.city

,tr.Region

,Tr.dmacode

FROM #fact_table ip

LEFT JOIN GEO2IP tr ON geo_range.STWithin(geometry::STGeomFromText('POINT('+CONVERT(varchar(20),ip.IP_Converted)+' 0)',0)) = 1

Here's the relatively simple DEP:

I admit DEP analysis is not a strong point of mine yet-- I know Table Scans are usually bad, but if the cost of it is 0% doesn't that mean it wouldn't be causing much of a slow down? Looking at this DEP, it seems to me that STContains really just isn't a very good function performance wise.