rs_.Find "MsgDate >=" + CStr(DateSerial(CInt(cmb_Year.Text), CInt(cmb_Month.BoundText), CInt(txt_Day.Text))), , adSearchForward, rs_First

где rs_ заполняется вызовом sp: select (поля) from tbl order by MsgDate,
rs_.moveFirst
rs_First = rs_.Bookmark

server-side, ReadOnly, 15000 записей (всего-то), одна табличка, по полю дата есть кластерный индекс
rs_.Find выполняется секунд 10, причем чем больше дата, тем дольше. Task manager при этом показывает загрузку процессора сервером примерно на 70% и клиентом на 30%

отсюда делаем вывод, что на сервере идет полный перебор по rs_ ?
Т.е. find не использует индексы? А если для получения ID нужной записи ипользовать запрос, то ни к чему тогда использовать полную выборку.

Читайте доки, они - рулез

Find действительно не использует индексы, да и как могут табличные индексы использоваться для поиска по результату запроса. Для этого надо seek, который adCmdTableDirect only, что неприятно, хотя и правильно.

Но что интересно, про ADO + Seek + SQLServer ни в книгах, ни в MSDN даже не упоминается.
Пока есть предположение, что Seek только для JetEngine.