Hola
Para realizar búsquedas yo me he acostumbrado a utilizar sentencias SQL, además, te recomendaría sustituir la el control DATA por el ADODC que en realidad es pasar de la tecnología DAO (obsoleta) a ADO (no tan obsoleta si hablamos de VB6, claro).
Respecto a tu consulta creo que te falta meter las comillas simples porque es un campo de texto, los campos numericos van sin nada, los de texto entre comillas simples y las fechas entre almohadillas
Código:
Agenda.Recordset.FindFirst "ApellidoPaterno= '" & nReg & "'"
Fíjate que incluyo la comillas simples
--Saludos--