como hacer Busquedas tipo regular Expression en SQL2000????

Amigos necesito hacer una busqueda en una tabla de clientes mas o menos
grande bajo estas condiciones:
si el usuario ingresa David Rodrigues, debo obtener una lista de todos
los nombres de clientes que coincidan tanto con el Nombre David or
tambien con el apellido rodrigues, algo parecido a esto

Nombres Codigo
David Castro 00001
Chirino Rodriguez 00005
Rodriguez Cesar 00003
David Rodriguez 00009
Cesar David 00002
..etc

alguien que me de una manito con esto

Gracias

Dany Acosta - Developers

Suponiendo que hicieras un store donde recibieras como parametros, nombre y
apellido.

SELECT * FROM CLIENTE
WHERE Nombre LIKE ISNULL(@NOMBRE+'%', '%')
AND APaterno LIKE ISNULL(@APATERNO+'%', '%')