Visual Basic - Cliente Servidor

Tengo una base de datos mdb montada en un servidor. Desarrolle un programa que accede a los datos de la misma a travez de un control dataenvironment. El problema es que para conectar la aplicacion a la base de datos uso una unidad de red. Esto desde determinados puntos del pais se torna muy lento abrir los recordsets, ya que algunas tablas cuentan hasta con 40.000 registros.
Pregunta...........como puedo hacer para agilizar esto?. Como genero una aplicacion cliente-servidor? Se pueden disminuir los tiempos de respuesta conservando los formatos en los controles de la aplicacion original y sin tocar la base de datos?
Gracias

Ante esta situación que deben abrir la BD desde diferentes sitios del país, como lo mensionas, es mejor tener un motor de BD, y no un archivo de datos como Access.

Entre los motores de BD están los gratuitos y los comerciales:
Gratuitos:
MySQL
MSDE (SQL Server, solo el motor, nada de herramientas de administración)
hay otras pero no recuerdo, sin embargo, también existen otras que pueden ser usadas desde Linux.

Comerciales:
SQL Server
Oracle
Sybase
DB2
entre otras.