Buscar información en archivo plano

Hola a todos
Ultimamente estoy como que muy pregunton

Bueno, yo tengo un programa que realiza búsquedas de
información sobre archivos planos

La búsqueda es secuencial, y aunque se encuentra la info
en ocaciones el proceso se hace demasiado lento, y tarda
demasiado en encontrar las cosas

De verdad quiero mejorar el proceso, no puedo usar xml,
ya que la infraestuctura no me lo permite

Una posible forma seria mediante archivos aleatorios,
pero según lo que entiendo estos requieren de longitudes
fijas , y los archivos de texto que yo manejo no se
caracterizan por esto, son completamente variables

Bueno estoy buscando ayuda de como mejorar mi proceso de
búsqueda, y así no tener tantos periodos de espera para
los usuarios

Estoy usando VB.net

Pero realmente lo que menos me importa es el lenguaje, lo
que realmente deseo es buscar la solución mas adecuada a
mi problema

Un saludo

Juan Carlos