I mean, I'm using the provided GiST-based R-Tree spatial index... Otherwise, I'm not really making any use of PostGIS and might as well look for other spacial DBs or write my own little data-structure like you mention (thanks for the link to VP-trees btw).

I was hoping that the performance of PostGIS's features could be improved with some know how.