Más que registros, la clave está en el tamaño del archivo de la bbdd.
Según Microsoft, en Access 2003 el tamaño máximo de la base de datos es de 2 Gigas. Puedes tener los registros que te quepan ahí (que evidentemente dependerán de la cantidad de campos, el tamaño de los mismos, si hay imágenes, etc.)
Pero además debes tener en cuenta qué equipo maneja esa base de datos (la memoria, el procesador, etc.) porque el rendimiento podría llegar a ser penoso.
Si necesitas más capacidad y potencia, puedes instalar el motor de SQL Server 2000 desktop, que es un SQL Server que corre en un PC, más limitado, y gratuito.
En la web de Microsoft puedes buscar por la expresión "msde" (Microsoft Data Engine). Te aparecerán ayudas para instalar, interfaz para administrarlo, etc.