la pregunta del millon de veces, QUE BASE DE DATOS ME RECOMIENDAN

[kipiloko]

Pues de las opciones existentes de hecho hiciste un muy buen trabajo limitanto que requieres y bajo que condiciones. Por lo que definitivamente deberias utilizar PostgreSQL que funciona tanto en cualquier Unix en tu caso un Linux y bajo Windows, se puede conectar via ODBC o por extension con PHP, Facilmente se comeria tus 10 millones de registros para lograr un performance excelente en cuanto a busquedas y aparte de ser estable, SQL bien implementado.

Para linux te bajas el tar y compilas e instalas en un SUSE o te consigues un RPM si te quieres evitar esto, en Debian un DEB, Mandrake ya lo trae asi como la mayoria de las versiones Server.

En Windows te bajas el MSI (www.postgresql.org) o WAPPO (http://veramextech-wappo.blogspot.com/) y listo. Ojo que wappo instala PHP y Apache, por lo que deberias tener cuidado si ya los tienes instalados leerte el manual.

No se que mas quieres saber sobre PostgreSQL para decantarte por el, pero es tu mejor opcion y aqui estoy para resolver tus dudas.