> MySQL, like PostGIS, stores it’s
> spatial index data in an R-tree
> structure so it can find stuff fast.
> An R-tree, like a B-tree, is organized
> in such a manner that it is optimized
> for retrieving only a small fraction
> of the total data in the table. It is
> actually faster to ignore the index
> for queries that need to read a large
> section of the table to return data or
> perform a huge join, a classic case
> which gives rise to many database
> forum [posters] complaining about
> a query that returns half their table
> "not using the new index they just
> created."

From 
https://web.archive.org/web/20120618090340/https://rickonrails.wordpress.com/2009/03/30/big-ole-mysql-spatial-table-optimization-tricks/

If you can fit all of your table data into memory, your performance is good. If/when you need to start doing disk reads, the performance quickly goes bad. Were you doing memory usage patterns of your mysql instance for the two cases: 30k rows vs. 3000k rows?