Общее время отклика = время выполнения запроса сервером + время передачи результата клиенту

Если вы наблюдаете резкое падение производительности при работе в локальной сети и с помощью модема, то скорее всего проблема именно в передача результатов, а не в выполнении запроса(хотя и его возможно оптимизировать).

LAN max 100Mbit
MODEM max 56Kbit(?) = 0.055Mbit, т.е. ~181 раз меньше чем в LAN (на практике наверное разница еще больше)

IMHO надо задуматься над количеством данных передаваемых в результате запросов.
Кстати где вы располагаете курсоры ADO на стороне клиента или сервера ?

Кроме того можно попробовать выполнять запросы асинхронно, "отвлекая" внимание пользователя разными сообщениями типа "Подождите еще немного" или простым таймером.

Можно попробовать выполнение одновременных(последовательных) независимых запросов в разных коннектах, хотя реальная физическая ширина канала от этого не возрастет, а реальная пропускная способность может и понизиться.

Или вообще перейти на работу с Terminal Server-ом и/или IIS+ASP, чтобы весь основой траффик происходил внутри LAN, а клиенту передавалась только картинка(VPN вроде бы у вас организован).

>Такое чуйство, что при каждом запросе идет поиск узла. Или я не прав?

Насколько я помню, согласно 7-ми уровневой модели OSI ADODB.Connection должен оперировать на 6-ом или 5-ом уровне(Presentation и Session) а VPN на 4-ом или 3-ем(Transport и Network). Возможно я ошибаюсь с номерами, но одно правильно, что VPN работает на более низком уровне. Таким образом ADO никоим образом не может влиять(непосредственно установкой каких-либо параметров) на более низкие уровни OSI.

Могу предположить, что когда вы использовали прямой дозвон без VPN ваш RAS и SQL сервера находились в одной сети. Т.е. в связке
Wks -- dialup -- RAS server -- lan -- SQL server
очень мало промежуточных хопов и конечно нет дополнительных операций над сетевыми пакета как в VPN

При реальной работе через Internet
Wks -- dialup -- Inet Provider -- ... anybody knows how many hops? .... -- VPN gate(RAS) -- lan -- SQL Server

на реальное время передачи пакета между сервером и рабочей станцией будет влиять каждый промежуточный хоп. Но ведь это Интернет и наверное не один вы создаете траффик через эти хопы. Кроме того возникает вопрос и о качестве обслуживания(Quality of Service, QoS). Если происходит потеря пакетов, то это не может не сказаться на общем времени передачи.

Резюме
IMHO с очень большой вероятностью это НЕ проблемы SQL и ADO. Опять же IMHO лучше для работы частных сетей через Интернет организовывать хардверный VPN.